1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

This is simply a heuristic.

Instead of comparing the element $e$ to the middle element at position $m$, compare it with each of the elements in range $m-c$ to $m+c$, for some constant $c$ say $5$ or $10$.

  1. If $e$ is smaller than the majority (approximately) of the elements in this range, move recursively to the left.

  2. If $e$ is larger than the majority (approximately) of the elements in this range, move recursively to the right.

  3. If the majority does not happen, the algorithm is already at an approximate position.

$\endgroup$
5
  • $\begingroup$ Well, then each comparison from m-c to m+c is considered one iteration(comparison), means it will take far longer to converge. $\endgroup$
    – nehem
    Sep 14 at 7:49
  • $\begingroup$ @nehem Right. There is a trade-off, choosing $c = 1$, will give you a less accurate result but converge fast. For larger $c$, it would be a more accurate result but it will converge slowly. As I said, it is simply a heuristic. You can even choose $c = 0 $, up to you. $\endgroup$ Sep 14 at 7:52
  • $\begingroup$ Yeah, the noise will get bigger at the far right side of the array, meaning c will keep increasing when the boundary moves towards right. That roughly puts n^2 performance. $\endgroup$
    – nehem
    Sep 14 at 7:55
  • $\begingroup$ @nehem I did not understand. In the question, it is not mentioned that noise is increasing towards right. $\endgroup$ Sep 14 at 9:22
  • $\begingroup$ My mistake, I must have mentioned. The way nature of the problem(words sorted by frequency of use) it’s evident that more noise to be expected at the right end of the spectrum. $\endgroup$
    – nehem
    Sep 14 at 13:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.