Algorytmy i struktury danych · Middle · Pytanie 16 z 75
Jak znaleźć wartość w posortowanej tablicy, którą obrócono, np. [4, 5, 6, 1, 2, 3], w O(log n)?
- 1Wyszukiwaniem liniowym, bo obrót psuje kolejność
- ✓Poprawna odpowiedź: Wyszukiwaniem binarnym, sprawdzając w każdym kroku, która połowa jest posortowana
- 3Najpierw posortować tablicę, potem zwykłe wyszukiwanie binarne
Wyjaśnienie
Porównaj arr[lo] z arr[mid], aby zobaczyć, która połowa jest uporządkowana, a potem sprawdź, czy cel mieści się w jej zakresie. Sortowanie najpierw kosztuje O(n log n), wyszukiwanie liniowe O(n).