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

Improve this question
$\endgroup$
4
  • $\begingroup$ It would be difficult to write an algorithm for this without some sort of precise definition of the problem. Certainly it seems like some relaxation of binary search would work, but in order to figure out exactly what relaxation would work, we would need to know what form the noise takes and how tolerant you are of error. $\endgroup$
    – nosyarg
    Commented Dec 13, 2023 at 17:33
  • $\begingroup$ In practice there is no definite way to sort the list, i.e there are more ways to sort the list. It's like ranking celebrities. Many different magazine organisations will come up with their own list which somewhat agrees with each other but not exactly agree with each others. $\endgroup$
    – nehem
    Commented Dec 16, 2023 at 12:31
  • $\begingroup$ I am still trying to determine what precisely you are trying to do. Does this mean you have several lists which have slightly different orders, a comparison query is only correct with some probability, or something else? $\endgroup$
    – nosyarg
    Commented Dec 17, 2023 at 21:24
  • $\begingroup$ I'm literally trying to do what the title says, Algorithm to find approximate position of element from a noisy(nearly) sorted list $\endgroup$
    – nehem
    Commented Dec 18, 2023 at 11:30

1 Answer 1

Reset to default
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.

Improve this answer
$\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
    Commented Sep 14, 2021 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$
    – Inuyasha Yagami
    Commented Sep 14, 2021 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
    Commented Sep 14, 2021 at 7:55
  • $\begingroup$ @nehem I did not understand. In the question, it is not mentioned that noise is increasing towards right. $\endgroup$
    – Inuyasha Yagami
    Commented Sep 14, 2021 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
    Commented Sep 14, 2021 at 13:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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