Search in Rotated Sorted Array

Sprawdź każdy indeks po kolei i zwróć pierwszy, którego wartość jest równa target. Jeśli pętla zakończy się bez znalezienia dopasowania, zwróć -1. Wartości są różne, więc pierwsze dopasowanie jest jedynym, a przeszukiwanie jest poprawne dla każdej listy, niezależnie od tego, czy jest obrócona.

Ignoruje to wszystko, o czym informuje cię treść zadania. Lista składa się z dwóch posortowanych ciągów, a mimo to przeszukiwanie liniowe odczytuje nawet wszystkie 5000 elementów, podczas gdy wyszukiwanie binarne wymaga około 13 porównań. Różnica rośnie wraz z rozmiarem danych wejściowych: milion elementów oznacza milion porównań, w porównaniu z około 20. Zadanie wymaga O(log n), więc jest to punkt wyjścia do ulepszenia, a nie odpowiedź.

Obrócona lista składa się z dwóch posortowanych części, a druga zaczyna się od najmniejszej wartości. Oznaczmy jej indeks jako k. Gdy znasz k, problem sprowadza się do zwykłego wyszukiwania binarnego: nums[k..n-1] jest posortowana i zawiera wartości od nums[k] do nums[n-1], a nums[0..k-1] jest posortowana i zawiera wszystkie większe wartości. Jedno porównanie target z nums[k] i nums[n-1] pozwala wybrać część do przeszukania.

Aby znaleźć k, wykonaj wyszukiwanie binarne, szukając spadku. Porównaj wartość środkową z ostatnią wartością zakresu, nums[hi]. Jeśli nums[mid] > nums[hi], wartości gdzieś za mid maleją, więc najmniejsza wartość znajduje się po prawej stronie: ustaw lo = mid + 1. W przeciwnym razie nums[mid..hi] rośnie bez spadku, więc najmniejsza wartość znajduje się na pozycji mid lub przed nią: ustaw hi = mid, pozostawiając mid w zakresie. Gdy lo zrówna się z hi, ten indeks to k.

Prześledź pierwszy przykład: [15, 19, 23, 2, 5, 8, 11] z target = 5. Środkowa wartość 2 nie jest większa niż 11, więc hi przyjmuje wartość 3; następnie 19 jest większe niż 2, więc lo przyjmuje wartość 2; potem 23 jest większe niż 2, więc lo przyjmuje wartość 3, a k = 3. Ponieważ 5 znajduje się między nums[3] = 2 a nums[6] = 11, przeszukaj indeksy od 3 do 6. Wyszukiwanie binarne znajduje 5 na indeksie 4. Dwa wyszukiwania binarne kosztują około 2 log2 n kroków.

Nie musisz wiedzieć, gdzie znajduje się punkt obrotu. Zachowaj standardową obietnicę wyszukiwania binarnego: jeśli target znajduje się na liście, jego indeks leży między lo a hi. Spójrz na środkowy indeks mid. Wartości maleją tylko raz w całej liście, więc ten spadek występuje w co najwyżej jednej z dwóch połówek wokół mid, a druga połowa jest posortowana.

Znajdź posortowaną połowę za pomocą jednego porównania. Jeśli nums[lo] ≤ nums[mid], lewa połowa nums[lo..mid] nie zawiera spadku i jest posortowana. Skoro wiesz już, że nums[mid] nie jest równe target, target może znajdować się w tej połowie tylko wtedy, gdy nums[lo] ≤ target < nums[mid]. Jeśli tak jest, ustaw hi = mid - 1; jeśli nie, target może znajdować się tylko w drugiej połowie, więc ustaw lo = mid + 1. Gdy nums[lo] > nums[mid], spadek znajduje się po lewej stronie, prawa połowa nums[mid..hi] jest posortowana, a rozstrzyga lustrzany warunek nums[mid] < target ≤ nums[hi]. Nigdy nie rozumujesz bezpośrednio o nieposortowanej połowie: target trafia do niej dokładnie wtedy, gdy nie może znajdować się w posortowanej połowie.

Prześledź pierwszy przykład: [15, 19, 23, 2, 5, 8, 11] przy target = 5. Zakres od 0 do 6 ma środkowy indeks 3, a jego wartość to 2. Ponieważ 15 jest większe od 2, prawa połowa [2, 5, 8, 11] jest posortowana, a 5 się w niej znajduje, więc lo przyjmuje wartość 4. Zakres od 4 do 6 ma środkowy indeks 5, a jego wartość to 8. Teraz nums[4] = 5 ≤ 8, lewa połowa [5, 8] jest posortowana i zawiera 5, więc hi przyjmuje wartość 4. Pod indeksem 4 znajduje się 5: zwróć 4.

Każdy krok zmniejsza zakres o połowę, tak jak w zwykłym wyszukiwaniu binarnym, więc pętla wykonuje się najwyżej około log2(n) + 1 razy: 13 kroków dla 5000 elementów, przy użyciu dwóch dodatkowych indeksów pamięci.