Tylko zapytaj wyrocznię: "czy x> = y?" raz na każdej iteracji twojego binarnego wyszukiwania. Jeśli otrzymasz tę samą odpowiedź dwa razy, to wiesz, że wyrocznia nie kłamała za pierwszym razem.
Na przykład, wyszukujesz x = 1, a pierwszy test testujesz przeciwko y = a, a oracle odpowiada x <. W drugim teście przetestuj przeciwko y = b, a oracle odpowiada x < b. Ponieważ używasz wyszukiwania binarnego, a wyrocznia mówi "<", a tablica jest posortowana, wiesz, że b < a. Dlatego, jeśli x < b, wiesz również, że x < a, a pierwsza odpowiedź nie była kłamstwem. Jeśli druga odpowiedź jest kłamstwem, a x> b, to nadal jest prawdą, że x < a, ponieważ wyrocznia może leżeć tylko raz.
Dzieje się tak, nawet jeśli odpowiedzi nie powrócą. Na przykład otrzymujesz trzy odpowiedzi: x < a, x> = b, x < c, wiesz, że c < a, przez twoje wyszukiwanie binarne, i tak musiało być prawdą, że x < a, a wyrocznia nie była leżąc, kiedy ci to powiedział.
Co się dzieje, gdy wyrocznia mówi kłamstwo? Jeśli kłamstwo było x < y, wtedy prawda była x> = y. Dlatego, gdy będziesz kontynuował wyszukiwanie binarne, od tego momentu sprawdzane liczby będą zbyt małe, a odpowiedź zawsze będzie "> =", aż dojdziesz do końca wyszukiwania binarnego. W tym momencie zdajesz sobie sprawę, że jeśli wyrocznia kłamała, kłamał, gdy ostatnio powiedział ci coś innego niż "> =". Więc ponownie uruchomiłeś wyszukiwanie binarne w punkcie, w którym wyrocznia cię okłamała i powiedziałeś "x < y".
To zawsze użyje < 2 log_2 n porównań, ale jeśli wyrocznia leży ci na początku wyszukiwania, będziesz musiał powtórzyć prawie log_2 n pracy, a więc nie dostaniesz log_2 n + o (log n) odpowiedź, której szukałeś. Tak więc powinieneś włączyć ideę sugerowaną przez nm. Jeśli otrzymasz taką samą odpowiedź, powiedzmy sqrt (log n) razy z rzędu, wtedy podejrzewasz, że wyrocznia mogła cię okłamać, i natychmiast ponownie zadajesz pytanie, które zapytał tuż przed tym, jak odpowiedzi zaczęły się powtarzać, zamiast czekać aż do końca wyszukiwania binarnego. Zgodnie z tą strategią, w najgorszym przypadku będziesz ponownie pytał o log n/sqrt (log n) razy, i zawsze będziesz łapał kłamstwo co najwyżej sqrt (log n) marnowanej pracy, która osiąga czas pracy szukam.
'2 * log_2 (N)' i 'log_2 (n) + O (log (N))' są oba 'O (log (N))'. Ukrytą stałą można użyć do zmiany bazy logów. Jesteś pewien, że to były kryteria rozwiązania? – phs
ok. Złożoność jest taka sama, czyli O (log (N)). Masz rację. Pytanie to jednak wymaga od mnie znalezienia algorytmu, który kosztowałby tylko porównania log_2 (n) + o (logn). Jest to mniej niż 2 * log_2 (n) porównań w naiwnym wyszukiwaniu binarnym, zadając dwa razy za każdym razem. Przykro mi, że nie wyjaśniam wystarczająco tego pytania. –
Pamiętaj, że musisz trzykrotnie poprosić o wykrycie prawidłowej odpowiedzi, jeśli jedna z odpowiedzi jest nieprawidłowa. – OleGG