Let's have a static function f(n) which for a given n returns only these answers "lower" or "higher" comparing against an imaginary number x

In a sorted list l = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20] It is obvious that using binary search we can find the position of the element in O'log(n) time.

Now let's have a sorted list but with some noise (somewhat sorted) l = [1, 2, 4, 3, 5, 6, 9, 7, 8, 11, 10, 12, 13, 16, 15, 14, 17, 20, 19, 18]

I'm looking for an algorithm that converges quickly to the approximate position of the imaginary x. I do have an algorithm (a modified binary search, relaxing the boundaries each side by 1.5x), Just wanted to hear from fresh perspective from other people.

Expectation: It is not allowed to sort the list, because the dataset is not sortable in a practical way.

The motivation to this question is, I'm writing a guessing game, containing list of publicly soured words sorted by popularity, the objective of the computer is to guess the number of words the player knows by asking as little questions as possible, where the player would respond "know" or "don't know", hence it's important for the algorithm to converge quickly

Let's have a static function f(n) which for a given n returns only these answers "lower" or "higher" comparing against an imaginary number x

In a sorted list l = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20] It is obvious that using binary search we can find the position of the element in O'log(n) time.

Now let's have a sorted list but with some noise (somewhat sorted) l = [1, 2, 4, 3, 5, 6, 9, 7, 8, 11, 10, 12, 13, 16, 15, 14, 17, 20, 19, 18]

I'm looking for an algorithm that converges quickly to the approximate position of the imaginary x. I do have an algorithm (a modified binary search, relaxing the boundaries each side, performing at logn), Just wanted to hear from fresh perspective from other people.

Expectation: It is not allowed to sort the list, because the dataset is not sortable in a practical way.

The motivation to this question is, I'm writing a guessing game, containing list of publicly soured words sorted by popularity, the objective of the computer is to guess the number of words the player knows by asking as little questions as possible, where the player would respond "know" or "don't know", hence it's important for the algorithm to converge quickly

Let's have a static function f(n) which for a given n returns only these answers "lower" or "higher" comparing against an imaginary number x

In a sorted list l = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20] It is obvious that using binary search we can find the position of the element in O'log(n) time.

Now let's have a sorted list but with some noise (somewhat sorted) l = [1, 2, 4, 3, 5, 6, 9, 7, 8, 11, 10, 12, 13, 16, 15, 14, 17, 20, 19, 18]

I'm looking for an algorithm that converges quickly to the approximate position of the imaginary x. I do have an algorithm (a modified binary search), Just wanted to hear from fresh perspective from other people.

Expectation: It is not allowed to sort the list, because the dataset is not sortable in a practical way.

The motivation to this question is, I'm writing a guessing game, containing list of publicly soured words sorted by popularity, the objective of the computer is to guess the word by asking as little questions as possible, where the player would respond "know" or "don't know", hence it's important for the algorithm to converge quickly

Let's have a static function f(n) which for a given n returns only these answers "lower" or "higher" comparing against an imaginary number x

In a sorted list l = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20] It is obvious that using binary search we can find the position of the element in O'log(n) time.

Now let's have a sorted list but with some noise (somewhat sorted) l = [1, 2, 4, 3, 5, 6, 9, 7, 8, 11, 10, 12, 13, 16, 15, 14, 17, 20, 19, 18]

I'm looking for an algorithm that converges quickly to the approximate position of the imaginary x. I do have an algorithm (a modified binary search, relaxing the boundaries each side by 1.5x), Just wanted to hear from fresh perspective from other people.

Expectation: It is not allowed to sort the list, because the dataset is not sortable in a practical way.

The motivation to this question is, I'm writing a guessing game, containing list of publicly soured words sorted by popularity, the objective of the computer is to guess the number of words the player knows by asking as little questions as possible, where the player would respond "know" or "don't know", hence it's important for the algorithm to converge quickly