1

Suppose you have a vector of array with N elements, and each element can be an integer between 0 and M. For example, "1, 3, 0, 4, 0" where N = 5 and M = 4.

I want to find this array by just doing an exhaustive search.

Please note that I have a special case where I can only do comparison with the whole array. That means I can "guess" an array, let's say "2, 0, 4, 1, 3" and then compare it with the original one.

Of course, I can easily do this by starting with "0, 0, 0, 0, 0" and just increment, but I'm looking for a faster method.

The only info I know about the original array is N, M, and that "0, 0, 0, 0, 0" and "M, M, M, M, M" have the least probability.

Also, I cannot know if part of my guess was right, I can only know if it was the right answer or not.

Thank you.

OneZ
  • 31
  • 3
    Do you have any other information of a "compare" result than "equal" or "not equal"? If not, then the only way is to try all the possible strings in any order, but "0,0,0,0,0" and "M,M,M,M,M" should be the last two. – z100 Jan 08 '16 at 19:04
  • No, my "guess" will only be answered with "equal" or "not equal". – OneZ Jan 08 '16 at 21:14

1 Answers1

0

Use binary search. Let $B_0=\mathbb E[X_N*Y_M] = \frac1{10}$. Let $B_1\sim\mathrm{Unif}\left(\frac1{10},\frac1{20}\right)\mathsf 1_{\{b_0>\frac1{10} \}}$ + $\mathrm{Unif}\left(0,\frac1{10}\right)\mathsf 1_{\left\{b_0<\frac1{10}\right\}}$. Then it will take $O(\log n)$ comparisons to come within $\varepsilon$ of the answer, for any $\varepsilon>0$.

Math1000
  • 36,983