how to do binary search in one lie model?

10

1

the question is like this: there is a sorted list of n numbers. Given x, find a number which is equal to x in the sorted list. Here we assume that x is indeed in the list. There is an oracle that can answer "yes" or "no" to your question "whether x>=y?". Unlike normal binary search, the oracle is allowed to lie once to your question. The most naive way to solve this problem is you ask each question twice to the oracle. If the two answers are the same, you know that the orale is not lying. This algorithm we need compare 2log_2(n) times. But this question ask me to find an algorithm that can find x using only log_2(n)+o(logn) comparisons.

I tried very hard but failed. Can anybody give me some advice on how to solve this problem? Thank you.

little_math

Posted 2012-01-30T01:13:15.223

Reputation: 73

42 * log_2(N) and log_2(n) + O(log(N)) are both O(log(N)). The hidden constant can be used to change the log base. Are you sure those were the solution criteria? – phs – 2012-01-30T02:35:49.540

ok. The complexity is the same, which is O(log(N)). You are right. However, the question want me to find an algorithm that cost only log_2(n)+o(logn) comparions. This is surly less than 2*log_2(n) comparisons in the naive binary search, asking twice each time. I am sorry that I don't make the question clear enough. – little_math – 2012-01-30T02:48:35.527

Note that you need to ask three times to detect right answer if one of the answers is lie. – OleGG – 2012-01-30T03:10:57.923

1You'd probably get a more detailed answer over at [cstheory.SE]. – darvids0n – 2012-01-30T03:23:29.197

yes. But the oracle can only lie once. If I ask twice and the oracle gives me different answer,then I should ask it a third time. However, it only take constant time because I know that the oracle would not give me a lie in the future. – little_math – 2012-01-30T03:25:03.127

Answers

3

Keep track of the interval you are in. If you need a total of k questions, check for consistency (whether you are in the interval you are supposed to be) every sqrt(k) steps. While checking for consistency you may ask each question twice to be sure. If you detect inconsistency, go back sqrt(k) steps. You will be asking no more than c*sqrt(k) additional questions.

n.m.

Posted 2012-01-30T01:13:15.223

Reputation: 70 315

I think you state out a general method to solve this kind of problem. sqrt(k) is just one possible way. May be log(k) can also help. The essencial point is that you have to check back in o(k) steps. Then the algorithm would finally give you k + o(k) complexity. – little_math – 2012-01-30T16:11:01.227

hehe, I think n.m means k questions, not the length of sorted list.Here we need logn questions so k=O(logn). – little_math – 2012-01-30T17:04:01.113

@hhn007: exactly, k questions. Why sqrt(k)? Because if you check every t steps, you may ask about t or about k/t extra questions, depending on whether the oracle lies near the start or near the end. To guarantee that both t and k/t are small you need to make them equal. – n.m. – 2012-01-30T19:11:49.087

yes. n.m. Yours are optimal methods. I mean o(k) can already meet the requirement of my question. hehe – little_math – 2012-01-30T19:57:08.070

2

Use the fact that after the oracle lied, binary search goes wrong way, and you get no change in the oracle's answer since that time (always >= or always <). If you get no change in the oracle's answer for log(log(n)) steps, check for interval consistency. If current interval is inconsistent, ask the oracle once more, and if still inconsistent, go back log(log(n)) + 1 steps and continue with normal binary search.

This procedure requires O(log(log(n))) consistency checks on average and up to log(log(n)) additional binary search steps.

Average number of additional questions is c*log(log(n)), maximum number of additional questions is log(n) / (log(log(n))) + log(log(n)).

Evgeny Kluev

Posted 2012-01-30T01:13:15.223

Reputation: 22 319

good. I think you are right. I also notice that when the oracle tell you a lie, after that it would always give you the same direction. It is clever to check the consistency after log(log(n)) steps. But why you add 2 in front of log(log(n))? why not just log(log(n))? Because there are at most log(n) / log(log(n)) times to check back. May be you mean log(n) / log(log(n))+log(log(n)) as the maximum number of additional questions? – little_math – 2012-01-30T16:00:42.340

Right, it will work with log(log(n)). – Evgeny Kluev – 2012-01-30T16:44:57.110

1

I guess solving this question in 3 * log(n) can be easy, by asking the inequality question three times at every step, and the decision is the majority one.

algo_freek

Posted 2012-01-30T01:13:15.223

Reputation: 41

1

Only ask the oracle the question: "is x >= y?" once on each iteration of your binary search. If you get the same answer twice, then you know the oracle didn't lie the first time.

For example, you are searching for x = 1, and the first test you test against y = a, and the oracle answers x < a. On the second test you test against y = b and the oracle answers x < b. Since you are using binary search, and the oracle said '<', and the array is sorted, you know that b < a. Therefore, if x < b, you also know that x < a, and the first answer was not a lie. If the second answer is a lie, and x > b, then it is still true that x < a, since the oracle can only lie once.

This is true even if the answers don't come back to back. For example you get three answers: x < a, x >= b, x < c, you know that c < a, by your binary search, and so it must have been true that x < a, and the oracle wasn't lying when he told you that.

So what happens when the oracle does tell a lie? If the lie was x < y, then the truth was x >= y. Therefore, when you continue your binary search, from that point on, the numbers you check will all be too small, and the answer will always be ">=", until you reach the bottom of the binary search. At that point, you realize that if the oracle lied, he lied the last time he told you something other than ">=". So you restart your binary search at the point where the oracle lied to you and said "x < y".

This will always use < 2 log_2 n comparisons, but if the oracle lies to you at the beginning of the search, then you will have to repeat nearly log_2 n work, and so you don't get log_2 n + o(log n) answer you were looking for. Thus, you should incorporate the idea suggested by n.m.. If you get the same answer, say sqrt(log n) times in a row, then you suspect that the oracle may have lied to you, and you immediately re-ask the question you asked right before the answers started repeating, instead of waiting until the bottom of the binary search. Following this strategy, you will re-ask a question log n / sqrt(log n) times in the worst case, and you will always catch the lie with at most sqrt(log n) wasted work, which achieves the running time you were looking for.

Joe

Posted 2012-01-30T01:13:15.223

Reputation: 328

thank you. You help me get a better understanding of the whole question. It is an interesting question isn't it? – little_math – 2012-01-30T16:02:19.627

Yes, it is interesting. n.m.'s answer is certainly correct, but I thought a little more elaboration would show the intuition more. Also, you only need to double-check the oracle's answer if he has been repeating himself. – Joe – 2012-01-30T19:28:23.053

+1 nice intuitive reasoning – cctan – 2012-11-02T05:56:48.817

0

You may want to change the classic binary search for this to work, how about try to ask the oracle in each iteration to compare 2 diffrent indexes of the array instead of just 1, something like:

assume Oracle(x,y) returns "x>=y?", assume every division is returning floor integer.
LyingOracleSearch(A,n,toFind)
1. if (n==0) return not found
2. if (A[0]==toFind) return found
3. if (Oracle(A[n/4],toFind) and Oracle(toFind,A[3n/4]) then
4.                      return LyingOracleSearch(A[(n/4)...(3n/4)],3n/4-n/4,toFind)
5. if (Oracle(A[n/4],toFind) and !Oracle(toFind,A[3n/4]) then
6.                      return LyingOracleSearch(A[0...(n/4)],n/4,toFind)
7. if (!Oracle(A[n/4],toFind) and Oracle(toFind,A[3n/4]) then
8.                      return LyingOracleSearch(A[(3n/4)...n],n-3n/4,toFind)
9. return LyingOracleSearch(A,n,toFind);  \\orcale lied!

I think that nails it, might be wrong tho.

it's complexity is the same as the original BS, but it is better then asking the oracle twice or more. notice that an element never gets compared to twice unless the oracle lies, so if it lies once or even k times where k is small-o(logn) then we are fine.

you may go to your favourite coding enviroment and try to code it, every time a comparison made, count it. try both this and the naive, and compare result, if im not mistaken, the naive should compare twice as much as this.

Notice tho, i was not too carefull with the indexes, you'll need to do some thinking to make sure i wasnt missing an index or wasnt repeating an index accidently.

Ofek Ron

Posted 2012-01-30T01:13:15.223

Reputation: 3 468

Nice idea anyway. However, can you assure that your algorithm is better than the naive binary search (each time ask twice)? I also tried many ways to divid the list and construct three indexes of one being "the oracle says x is inside it", the second one" the oracle says x is outside it for once", the third one "the oracle says x is outside it for twice". Then I can throw away the elements in the third one. However, this algorithm does seem to work after the first step. – little_math – 2012-01-30T16:07:19.577

edited, see if you get it. – Ofek Ron – 2012-01-30T16:43:17.780

ok, I will try that. Thanks anyway. – little_math – 2012-01-30T17:05:10.753