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.
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$.