0Pricing
Coding Interview Prep · Lekcja

Klasyczne wyszukiwanie binarne: lewo, prawo, środek

Zaimplementują Państwo iteracyjne i rekurencyjne wyszukiwanie binarne, dopracują szczegóły off-by-one dla granic lo/hi oraz sprawdzą poprawność na danych brzegowych.

Klasyczne wyszukiwanie binarne: lewo, prawo, środek to bezpłatna lekcja Coding Interview Prep na CoddyKit. To lekcja 1 z 4. Możesz przeczytać całą lekcję poniżej za darmo — a potem ćwiczyć ją interaktywnie w przeglądarce z wbudowanym edytorem kodu i tutorem AI dostępnym 24/7. To część ścieżki edukacyjnej Coding Interview Prep, a Twój postęp synchronizuje się między webem a aplikacją CoddyKit. Kurs Coding Interview Prep zawiera 4 lekcji w sumie.

Dlaczego wyszukiwanie binarne ma znaczenie

Wyszukiwanie binarne zmniejsza koszt liniowego przeszukiwania z O(n) do O(log n), dzieląc przestrzeń wyszukiwania na pół w każdym kroku. W tablicy zawierającej milion elementów wyszukiwanie liniowe wymaga do 1 000 000 porównań, podczas gdy wyszukiwanie binarne wymaga najwyżej 20. Ta wydajność sprawia, że jest to jeden z najczęściej sprawdzanych algorytmów na rozmowach rekrutacyjnych dotyczących programowania.

Kluczowa obserwacja polega na tym, że posortowana tablica pozwala po jednym porównaniu zdecydować, którą połowę pozostałych danych można całkowicie odrzucić.

Schemat lewa, środek, prawa

Wyszukiwanie binarne używa trzech wskaźników indeksu: lo (lewa granica), hi (prawa granica) oraz mid (środek). W każdej iteracji oblicza się mid = (lo + hi) // 2 i porównuje szukaną wartość z arr[mid]. Jeśli szukana wartość jest mniejsza, należy ustawić hi = mid - 1; jeśli większa — lo = mid + 1; jeśli równa — została znaleziona.

Pętla działa, dopóki lo <= hi. Jeśli zakończy się bez znalezienia szukanej wartości, należy zwrócić -1.

def binary_search(arr, target):
    lo, hi = 0, len(arr) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

print(binary_search([1, 3, 5, 7, 9, 11], 7))  # 3
print(binary_search([1, 3, 5, 7, 9, 11], 6))  # -1

Unikanie przepełnienia liczby całkowitej w mid

Wyrażenie mid = (lo + hi) // 2 może powodować przepełnienie liczby całkowitej w językach używających liczb całkowitych o stałej szerokości (Java, C++). Liczby całkowite w Pythonie mają dowolną precyzję, więc przepełnienie nigdy nie występuje, ale na rozmowie rekrutacyjnej nadal oczekuje się znajomości bezpiecznej alternatywy: mid = lo + (hi - lo) // 2.

Ta postać oblicza ten sam środek, ale dodaje do lo tylko połowę odległości, zamiast najpierw sumować oba wskaźniki. Wspomnienie o tym podczas rozmowy świadczy o świadomości zagadnień niskopoziomowych.

# Safe mid calculation (important in Java/C++, good habit in Python too)
lo, hi = 0, 1_000_000_000
mid_unsafe = (lo + hi) // 2   # fine in Python
mid_safe   = lo + (hi - lo) // 2  # same result, no overflow risk
print(mid_unsafe == mid_safe)  # True

Granice włącznie a granice wyłącznie

Jednym z najtrudniejszych elementów wyszukiwania binarnego jest wybór, czy hi wskazuje na ostatni poprawny indeks (granica włącznie, hi = len(arr) - 1), czy na pozycję za końcem tablicy (granica wyłącznie, hi = len(arr)). Różne konwencje wymagają różnych warunków pętli i aktualizacji granic.

Przy granicach włącznie należy użyć while lo <= hi oraz aktualizacji hi = mid - 1. Przy granicach wyłącznie należy użyć while lo < hi oraz aktualizacji hi = mid. Mieszanie konwencji jest najczęstszą przyczyną błędów w implementacjach wyszukiwania binarnego.

# Exclusive hi variant — useful for bisect-style lower-bound
def search_exclusive(arr, target):
    lo, hi = 0, len(arr)  # hi is one past last
    while lo < hi:          # strictly less than
        mid = lo + (hi - lo) // 2
        if arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid         # NOT mid - 1
    return lo if lo < len(arr) and arr[lo] == target else -1

print(search_exclusive([2, 4, 6, 8, 10], 6))  # 2

Rekurencyjne wyszukiwanie binarne

Wyszukiwanie binarne można zapisać rekurencyjnie, przekazując zaktualizowane granice lo i hi przez stos wywołań. Każde rekurencyjne wywołanie zmniejsza przestrzeń wyszukiwania o połowę, więc głębokość wynosi O(log n). Przypadkiem bazowym jest lo > hi (nie znaleziono) lub arr[mid] == target (znaleziono).

Wersja iteracyjna jest preferowana w kodzie produkcyjnym, ponieważ eliminuje narzut ramek stosu, ale wersja rekurencyjna wyraźniej pokazuje strukturę metody dziel i zwyciężaj na tablicy podczas rozmowy technicznej.

def binary_search_rec(arr, target, lo, hi):
    if lo > hi:
        return -1
    mid = lo + (hi - lo) // 2
    if arr[mid] == target:
        return mid
    elif arr[mid] < target:
        return binary_search_rec(arr, target, mid + 1, hi)
    else:
        return binary_search_rec(arr, target, lo, mid - 1)

arr = [1, 3, 5, 7, 9, 11]
print(binary_search_rec(arr, 9, 0, len(arr) - 1))  # 4

Przypadki brzegowe: pusta tablica, jeden element

Odporne wyszukiwanie binarne musi obsługiwać przypadki brzegowe bez powodowania awarii. Trzy najczęstsze przypadki to: pusta tablica (pętla się nie wykona i poprawnie zostanie zwrócone -1), tablica jednoelementowa (mid jest równy lo i hi, więc wystarczy jedno porównanie) oraz szukane wartości spoza zakresu (lo ostatecznie przekroczy hi i zostanie zwrócone -1).

Przed przejściem do dodatkowych pytań podczas rozmowy rekrutacyjnej należy zawsze sprawdzić implementację na takich danych wejściowych.

def binary_search(arr, target):
    lo, hi = 0, len(arr) - 1
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

print(binary_search([], 5))       # -1  (empty)
print(binary_search([7], 7))      # 0   (single, found)
print(binary_search([7], 3))      # -1  (single, not found)
print(binary_search([1,3,5], 0))  # -1  (below range)
print(binary_search([1,3,5], 9))  # -1  (above range)

Złożoność czasowa i pamięciowa

Wyszukiwanie binarne ma złożoność czasową O(log n), ponieważ każde porównanie dzieli przestrzeń wyszukiwania na pół. Po k porównaniach pozostaje n/2^k elementów; wyszukiwanie kończy się, gdy ta wartość osiągnie 1, więc k = log₂ n.

Złożoność pamięciowa wynosi O(1) dla wersji iteracyjnej (używa ona tylko trzech zmiennych całkowitoliczbowych) oraz O(log n) dla wersji rekurencyjnej, ze względu na głębokość stosu wywołań. Na rozmowie rekrutacyjnej należy zawsze podawać obie wartości i preferować wersję iteracyjną, gdy pamięć jest ograniczona.

import math

for n in [10, 100, 1000, 1_000_000, 1_000_000_000]:
    steps = math.ceil(math.log2(n + 1))
    print(f'n={n:>12,}  max comparisons={steps}')

Wyszukiwanie dokładnego dopasowania a granicy

Klasyczne wyszukiwanie binarne zwraca dowolny indeks, pod którym występuje szukana wartość. Jednak wiele zadań rekrutacyjnych wymaga znalezienia pierwszego lub ostatniego wystąpienia szukanej wartości. W takich przypadkach należy kontynuować wyszukiwanie nawet po znalezieniu dopasowania — zamiast od razu zwracać wynik trzeba zawęzić granicę i szukać dalej.

Podczas wyszukiwania pierwszego wystąpienia po znalezieniu arr[mid] == target należy zapisać mid jako kandydata i ustawić hi = mid - 1. Aby znaleźć ostatnie wystąpienie, należy ustawić lo = mid + 1.

def first_occurrence(arr, target):
    lo, hi, result = 0, len(arr) - 1, -1
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        if arr[mid] == target:
            result = mid
            hi = mid - 1   # keep searching left
        elif arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return result

print(first_occurrence([1, 2, 2, 2, 3], 2))  # 1

Korzystanie z modułu bisect w Pythonie

Biblioteka standardowa Pythona udostępnia funkcje bisect.bisect_left(arr, x) i bisect.bisect_right(arr, x) do użycia w gotowym kodzie produkcyjnym. bisect_left zwraca skrajny lewy indeks, pod którym można wstawić x, aby zachować sortowanie tablicy, skutecznie znajdując pierwszą pozycję, dla której arr[i] >= x.

Rozmówcy rekrutacyjni mogą zezwolić na użycie bisect; należy to zawsze wcześniej potwierdzić. Nadal niezbędna jest znajomość działania tego modułu od wewnątrz (wykorzystuje on wyszukiwanie binarne o złożoności O(log n)).

import bisect

arr = [1, 2, 2, 2, 3, 5]

print(bisect.bisect_left(arr, 2))   # 1  (first 2)
print(bisect.bisect_right(arr, 2))  # 4  (after last 2)

# Check if target exists
target = 3
idx = bisect.bisect_left(arr, target)
print(idx < len(arr) and arr[idx] == target)  # True

Częste pułapki w wyszukiwaniu binarnym

Większość błędów w wyszukiwaniu binarnym podczas rozmów rekrutacyjnych powodują trzy pomyłki. Po pierwsze, nieprawidłowy warunek pętli: użycie < zamiast <= przy granicach włącznie powoduje pominięcie ostatniego pozostałego elementu. Po drugie, niepoprawna aktualizacja granicy: pominięcie +1 lub -1 tworzy nieskończoną pętlę, gdy lo == hi. Po trzecie, operowanie na nieposortowanej tablicy: wyszukiwanie binarne jest poprawne wyłącznie dla posortowanych danych.

Przed napisaniem dowolnego wyszukiwania binarnego należy powiedzieć na głos: „Tablica jest posortowana, moje granice są włącznie, a pętla działa, dopóki lo <= hi”.

# BUG: infinite loop when lo == hi because hi = mid never moves past lo
def buggy(arr, target):
    lo, hi = 0, len(arr) - 1
    while lo < hi:              # should be lo <= hi for exact-match
        mid = lo + (hi - lo) // 2
        if arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid            # stops, but never returns mid when found
    return lo if arr[lo] == target else -1

print(buggy([1, 3, 5, 7], 7))  # 3 (works here by luck)
print(buggy([1, 3, 5, 7], 1))  # 0 (correct)
print(buggy([1, 3, 5, 7], 4))  # -1 (correct)

Wskazówki dotyczące wyszukiwania binarnego na rozmowie rekrutacyjnej

Gdy zadanie dotyczy posortowanej tablicy, funkcji monotonicznie rosnącej lub przestrzeni wyszukiwania, którą można podzielić na pół, należy od razu rozważyć wyszukiwanie binarne. Podczas rozmowy rekrutacyjnej należy wyjaśniać tok rozumowania: „Ponieważ tablica jest posortowana, przy każdym porównaniu mogę odrzucić połowę elementów, co daje O(log n)”.

Należy zawsze sprawdzić rozwiązanie na co najmniej trzech danych wejściowych: wartości znajdującej się na początku, wartości znajdującej się na końcu oraz wartości, której nie ma w tablicy. Samodzielne podanie złożoności — „czas O(log n), pamięć O(1)” — jeszcze przed zadaniem pytania świadczy o solidnych podstawach.

Szybkie sprawdzenie

Sprawdź swoją wiedzę na temat zagadnień z kursu Data Structures & Algorithms — Coding Interview Prep omówionych w tej lekcji.

Podsumowanie lekcji

W tej lekcji nauczyli się Państwo, że: wyszukiwanie binarne dzieli przestrzeń wyszukiwania na pół w każdym kroku, osiągając złożoność czasową O(log n), konwencja granic włącznie używa lo <= hi oraz aktualizacji lo = mid+1 i hi = mid-1, a aby znaleźć pierwsze lub ostatnie wystąpienie, należy kontynuować wyszukiwanie po znalezieniu dopasowania, zamiast od razu zwracać wynik. Następnie omówimy zastosowanie wyszukiwania binarnego do tablic obróconych i nieposortowanych.

Często zadawane pytania

Czy lekcja „Klasyczne wyszukiwanie binarne: lewo, prawo, środek” jest bezpłatna?

Tak — pełny tekst „Klasyczne wyszukiwanie binarne: lewo, prawo, środek” jest dostępny za darmo tutaj w sieci. Aby ćwiczyć ją interaktywnie (wbudowany edytor kodu i tutor AI dostępny 24/7) i odblokować resztę kursu Coding Interview Prep, przejdź na CoddyKit PRO. Kurs Coding Interview Prep zawiera 4 lekcji w sumie.

Co nauczysz się w „Klasyczne wyszukiwanie binarne: lewo, prawo, środek”?

Zaimplementują Państwo iteracyjne i rekurencyjne wyszukiwanie binarne, dopracują szczegóły off-by-one dla granic lo/hi oraz sprawdzą poprawność na danych brzegowych. Ćwiczysz Coding Interview Prep z praktycznym kodem, który uruchamiasz bezpośrednio w przeglądarce, a tutor AI dostępny 24/7 odpowiada na Twoje pytania podczas pracy nad lekcją.

Czy potrzebuję doświadczenia, aby zacząć Coding Interview Prep?

Nie wymagamy żadnego doświadczenia. Coding Interview Prep w CoddyKit jest strukturyzowany dla początkujących i zaawansowanych użytkowników, więc możesz zacząć tutaj lub od początku i uczyć się w swoim tempie. To lekcja 1 z 4.

Ile czasu zajmuje lekcja „Klasyczne wyszukiwanie binarne: lewo, prawo, środek”?

Większość lekcji CoddyKit trwa około 5–10 minut. Każda lekcja to mały, interaktywny krok, dzięki czemu robisz systematyczne postępy i zawsze wracasz dokładnie do tego samego miejsca — na webie i w aplikacji.

Czy mogę pisać i uruchamiać kod w tej lekcji Coding Interview Prep?

Tak. Każda lekcja Coding Interview Prep zawiera wbudowany edytor kodu, więc piszesz i uruchamiasz prawdziwy kod bezpośrednio w przeglądarce i od razu otrzymujesz sprzężenie zwrotne od AI — bez konfiguracji na komputerze.

Wszystkie lekcje w tym kursie

  1. Klasyczne wyszukiwanie binarne: lewo, prawo, środek
  2. Wyszukiwanie binarne w tablicach obróconych i nieposortowanych
  3. Dolna i górna granica
  4. Wyszukiwanie binarne w przestrzeni odpowiedzi
← Powrót do Coding Interview Prep