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.

4

`2 * 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.540ok. 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