Menu
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.
368
Step-by-step Binary Search Algorithm: We basically ignore half of the elements just after one comparison. Compare x with the middle element. If x matches with the middle element, we return the mid index. Else If x is greater than the mid element, then x can only lie in the right half subarray after the mid element.
When we binary search on an answer, we start with a search space of size N which we know the answer lies in. Then each iteration of the binary search cuts the search space in half, so the algorithm tests O ( log N ) \mathcal{O}(\log N) O(logN) values.
Binary Search is a searching algorithm for finding an element's position in a sorted array. In this approach, the element is always searched in the middle of a portion of an array. Binary search can be implemented only on a sorted list of items. If the elements are not sorted already, we need to sort them first.
Since 64=2log2(64)=26 64 = 2 log 2 ( 64 ) = 2 6 , the number of comparisons required for an array of length 64 is 1+log2(64)=1+6=7 1 + log 2 ( 64 ) = 1 + 6 = 7 .
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.
85
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)).
33
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
