Binary Search
Otrzymujesz listę liczb całkowitych nums, posortowaną rosnąco, bez powtarzających się wartości, oraz liczbę całkowitą target. Zwróć indeks target w nums, licząc od 0, lub -1, jeśli nie ma jej na liście. Dąż do złożoności czasowej O(log n), co oznacza, że nie możesz sprawdzić każdego elementu.
Funkcja
- numsinteger-array
- posortowana lista różnych liczb całkowitych
- targetinteger
- wartość, której należy szukać
- Zwracainteger
- indeks target w nums albo -1, jeśli go tam nie ma
Ograniczenia
1 ≤ nums.length ≤ 104-104 ≤ nums[i], target ≤ 104numsjest posortowana w ściśle rosnącej kolejności, więc każda wartość występuje raz.
Przykłady
- Wejście
- nums = [-7, -2, 0, 4, 9, 15, 23]target = 9
- Wyjście
- 4
- Wyjaśnienie
nums[4]ma wartość 9. Wyszukiwanie sprawdza indeks 3 (wartość 4 — za mała), następnie indeks 5 (wartość 15 — za duża), a potem indeks 4, gdzie znajduje 9.
- Wejście
- nums = [1, 3, 5, 8, 13, 21]target = 10
- Wyjście
- -1
- Wyjaśnienie
- 10 znalazłoby się między 8 a 13, a żadna z tych liczb nie jest równa 10, więc 10 nie ma na liście. Zakres wyszukiwania się zawęża, aż
loprzekroczyhi, a funkcja zwraca-1.
+15 ukrytych testów przy wysłaniu
Pytanie dodatkowe
Jeśli wartości w nums mogą się powtarzać, jak zwrócić pierwszy indeks target, nadal w czasie O(log n)?
Podpowiedzi
Otwieraj je po kolei. Każda zdradza trochę więcej.
Lista jest posortowana. Jeśli porównasz
targetz jednym elementem pośrodku, co mówi ci to o wszystkich elementach po jednej stronie tego elementu?Jeśli
nums[mid] < target, tonums[mid]i wszystko na lewo od niego są za małe, więctargetmoże znajdować się tylko po prawej stronie. Jedno porównanie odrzuca połowę kandydatów.Utrzymuj dwa indeksy,
loihi, wokół części listy, w której nadal może znajdować siętarget. Porównaj z elementem środkowym, przesuńlolubhipoza niego i zakończ, gdy znajdziesztargetalboloprzekroczyhi.
Rozwiązanie
Odczytywanie elementów po kolei pozwala znaleźć target, ale pomija jeden fakt, który sprawia, że problem jest interesujący: lista jest posortowana. Jedno porównanie ze środkowym elementem mówi, w której połowie nadal może znajdować się target, więc na każdym kroku możesz odrzucić połowę kandydatów. Lista zawierająca 10^4 elementów wymaga wtedy najwyżej 14 porównań zamiast 10000.
Skanuj od lewej do prawej
Intuicja
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, target nie ma na liście, więc zwróć -1. Każdy element jest porównywany raz, co sprawia, że odpowiedź jest poprawna dla każdej listy, posortowanej lub nie.
Problemem jest ta ogólność. Lista zawierająca 10^4 elementów wymaga do 10000 porównań, a ilość pracy rośnie proporcjonalnie do n. Przeszukiwanie nie wykorzystuje faktu, że nums jest posortowana, więc nie osiąga granicy O(log n), której wymaga zadanie. Możesz zakończyć wcześniej, gdy tylko wartość przekroczy target, ale w najgorszym przypadku i tak odczytasz całą listę.
Algorytm
- Dla każdego indeksu
iod 0 don-1porównajnums[i]ztarget. - Jeśli są równe, zwróć
i. - Po pętli zwróć
-1.
def search(nums, target):
for i, value in enumerate(nums):
if value == target:
return i
return -1Wyszukiwanie binarne z dwoma indeksami
Intuicja
Utrzymuj dwa indeksy: lo i hi, oraz jedno założenie: jeśli target znajduje się na liście, jego indeks leży między lo a hi, włącznie. Na początku ten zakres obejmuje całą listę: od 0 do n-1. Sprawdź środkowy indeks mid. Jeśli nums[mid] jest równe target, koniec. Jeśli jest mniejsze, to ponieważ lista jest posortowana, każdy element aż do mid również jest mniejszy, więc ustaw lo na mid + 1. Jeśli jest większe, ustaw hi na mid - 1. Po każdym z tych ruchów założenie nadal jest spełnione.
Prześledź pierwszy przykład: [-7, -2, 0, 4, 9, 15, 23] z target = 9. Zakres od 0 do 6 ma środkowy indeks 3, którego wartość wynosi 4 — to za mało, więc zakres zmienia się na 4–6. W jego środku, pod indeksem 5, znajduje się 15 — to za dużo, więc zakres zmienia się na 4–4. Pod indeksem 4 znajduje się 9: zwróć 4.
Jeśli brakuje target, zakres będzie się zmniejszał, aż lo przekroczy hi. Zakres jest wtedy pusty, a założenie mówi, że target nigdzie się nie znajduje, więc zwróć -1. Każdy krok zmniejsza zakres o połowę, więc pętla wykona najwyżej około log2(n) + 1 iteracji: 14 kroków dla 10^4 elementów. Dwa indeksy to cała dodatkowa pamięć, której potrzebujesz.
Algorytm
- Ustaw
lo = 0ihi = n-1. - Dopóki
lo ≤ hi, obliczmid = lo + (hi - lo) / 2. - Jeśli
nums[mid]jest równetarget, zwróćmid. - Jeśli
nums[mid] < target, ustawlo = mid + 1; w przeciwnym razie ustawhi = mid - 1. - Gdy pętla się zakończy, zwróć
-1.
def search(nums, target):
lo, hi = 0, len(nums) - 1 # target, if present, sits in nums[lo..hi]
while lo <= hi:
mid = (lo + hi) // 2
if nums[mid] == target:
return mid
if nums[mid] < target:
lo = mid + 1 # nums[mid] and everything left of it is too small
else:
hi = mid - 1 # nums[mid] and everything right of it is too big
return -1
Pułapki i przypadki brzegowe
Wyszukiwanie binarne jest krótkie i niemal każdy błąd to pomyłka o jeden na krańcach zakresu.
- Wykonywanie pętli przy
lo < hi, gdyhizaczyna od ostatniego indeksu. Pętla kończy się, gdy jeden kandydat nie został jeszcze sprawdzony, więcnums = [5]przytarget = 5zwraca-1. Przy zakresie domkniętym wykonuj pętlę, dopókilo ≤ hi. - Przypisywanie
lo = midlubhi = midprzy zakresie domkniętym. Gdyloihisą sąsiadami,midjest równelo, a zakres nigdy się nie zmniejsza: powstaje nieskończona pętla. Wartośćnums[mid]została już sprawdzona, więc przesuń się poza nią, używającmid + 1lubmid - 1. - Obliczanie
(lo + hi) / 2przy użyciu liczby całkowitej o stałej szerokości. Suma przepełnia się, gdy indeksy przekroczą około10^9. Podane tu limity są znacznie niższe, ale warto wyrobić sobie bezpieczny nawyk używanialo + (hi - lo) / 2. - Zwracanie
lo, gdy brakujetarget. Po pętlilojest miejscem wstawienia, które jest prawidłowym indeksem, a nie-1. - Zapominanie o przesunięciu w Lua i R. Ich listy zaczynają się od 1, więc zwracany indeks to pozycja minus 1.
Najczęstsze pytania4
Jaka jest złożoność czasowa wyszukiwania binarnego?
O(log n). Każde porównanie zmniejsza o połowę zakres, w którym może jeszcze znajdować się szukany element, więc po k krokach pozostaje co najwyżej n / 2^k kandydatów. Lista zawierająca 10^4 elementów wymaga co najwyżej 14 porównań, a lista zawierająca 10^9 elementów — co najwyżej 30. Wersja iteracyjna używa dodatkowej pamięci O(1).
Dlaczego wyszukiwanie binarne wymaga posortowanej tablicy?
Krok polegający na odrzuceniu połowy listy opiera się na kolejności. Gdy nums[mid] < target, sortowanie gwarantuje, że każdy element na lewo od mid jest również mniejszy niż target, więc żaden z nich nie może być szukanym elementem. W nieposortowanej liście to porównanie nic nie mówi o pozostałych elementach i musisz sprawdzić je wszystkie.
Czy wyszukiwanie binarne powinno być iteracyjne czy rekurencyjne?
Oba rozwiązania są poprawne i oba działają w czasie O(log n). Wersja rekurencyjna wywołuje samą siebie dla jednej połowy i wykorzystuje O(log n) miejsca na stosie; wersja iteracyjna przesuwa lo i hi w pętli i wykorzystuje O(1). Osoby przeprowadzające rozmowy kwalifikacyjne zwykle oczekują pętli, która pozwala uniknąć limitu rekurencji.
Jak uniknąć przepełnienia przy obliczaniu indeksu środkowego?
Zapisz mid = lo + (hi - lo) / 2 zamiast (lo + hi) / 2. Oba zapisy dają ten sam indeks, ale w drugim najpierw dodawane są dwa indeksy, a w 32-bitowej liczbie całkowitej ich suma przepełnia się, gdy indeksy przekroczą około 1.07 × 10^9. Python i Ruby obsługują liczby całkowite o nieograniczonym zakresie, więc tam krótszy zapis jest bezpieczny.
Podobne zadania
Zadania oparte na tych samych pomysłach. Rozwiązanie dwóch lub trzech utrwala schemat.
Python
def search(nums, target):
# Wpisz kod tutajPrzypadek 1
Przypadek 2
Wejście
nums = [-7, -2, 0, 4, 9, 15, 23] target = 9
Oczekiwane
4