Wyszukiwanie binarne to jeden z najczęściej testowanych algorytmów na rozmowach technicznych — zarówno samo w sobie, jak i jako wzorzec dla problemów typu „find first true in monotonic predicate". Bez niego nie odpowiesz precyzyjnie na pytania o szukanie w sorted, znajdowanie granicy lub optymalizację z O(n) do O(log n).
Ten artykuł pokazuje binary search jako narzędzie algorytmiczne: definicję, intuicję halve-the-space, warunki konieczne, klasyczną implementację z pułapkami off-by-one, lower/upper bound, wzorzec find first true i sygnały rozpoznawcze zadań. Implementacja w Pythonie dla zwięzłości — wzorzec jest language-agnostic (analogicznie w Java, C++, JavaScript, Ruby).
Pozostaję w obrębie wyszukiwania w sorted array i wzorca monotonic predicate. Drzewa BST jako wariant binary search (też dziel-i-zwyciężaj, ale na strukturze wskaźnikowej) to powiązany ale osobny temat.
Co to jest wyszukiwanie binarne
Wyszukiwanie binarne to algorytm znajdowania elementu w posortowanej kolekcji przez wielokrotne dzielenie aktualnego zakresu na połowy. Porównuje szukaną wartość ze środkiem i odrzuca część w której wynik nie może leżeć.
Intuicja: wyobraź sobie słownik. Otwierasz na środku, sprawdzasz pierwszą literę, decydujesz czy szukasz w lewej, czy prawej połowie. Powtarzasz aż znajdziesz słowo lub stwierdzisz że go nie ma. Każde porównanie odrzuca połowę pozostałych stron.
search 9 in [2, 4, 7, 9, 13]:
step 1: [2, 4, 7, 9, 13] mid=7, 9 > 7 → odrzuć lewą
step 2: [9, 13] mid=9, found! ✓
3 elementy zakresu → 2 porównania (zamiast 5 dla liniowego)
Warunek posortowania jest częścią definicji, nie drobnym usprawnieniem. Jeśli element środkowy jest mniejszy od celu, lewa połowa nie zawiera odpowiedzi; jeśli większy, odpada prawa połowa. Bez sortowania algorytm zwraca losowe wyniki.
def binary_search(values, target):
left = 0
right = len(values) - 1
while left <= right:
mid = (left + right) // 2
if values[mid] == target:
return mid
if values[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
print(binary_search([2, 4, 7, 9, 13], 9)) # expected_output: 3
print(binary_search([2, 4, 7, 9, 13], 5)) # expected_output: -1
Trace dla binary_search([2, 4, 7, 9, 13], 9):
Krok 1: left=0, right=4, mid=2, values[2]=7. 9 > 7 → left = 3.
Krok 2: left=3, right=4, mid=3, values[3]=9. Znaleziono → return 3.
Klucz: 2 porównania dla 5 elementów. Dla 1 mln elementów to ~20 porównań, dla 1 mld — ~30. Skalowanie logarytmiczne.
Pułapka: zwykłe szukanie w nieposortowanej liście NIE staje się binarne tylko dlatego że używa if. Mechanizm błędu: kandydat pisze pętlę for x in values: if x == target: ... i mówi „log n bo używam warunku" — ale każdy element musi zostać sprawdzony, więc faktyczny koszt to O(n). Kluczowe jest odrzucanie połowy uporządkowanego zakresu po każdym porównaniu.
Dlaczego złożoność wynosi O(log n)
W każdym kroku algorytm zmniejsza rozmiar problemu mniej więcej o połowę. Po jednym porównaniu zostaje n/2 elementów, po dwóch n/4, po trzech n/8, aż zakres stanie się pusty. To matematyczna definicja logarytmu base-2.
Intuicja: pytanie „ile razy mogę podzielić n przez 2 zanim dotrę do 1?" ma odpowiedź log₂(n). Dla n = 1024 = 2^10 potrzeba 10 podziałów. Dla n = 1 mln ≈ 2^20 — 20 podziałów. Podwojenie danych dodaje tylko jeden krok. Szczegóły asymptotyki: Big O w 10 minut.
def max_binary_steps(size):
steps = 0
remaining = size
while remaining > 0:
steps += 1
remaining //= 2
return steps
print(max_binary_steps(1)) # expected_output: 1
print(max_binary_steps(1024)) # expected_output: 11
print(max_binary_steps(1_000_000)) # expected_output: 20
Pułapka: samo wyszukiwanie ma koszt O(log n), ale przygotowanie posortowanej kolekcji kosztuje O(n log n) — szczegóły kosztu sortowania: Algorytmy sortowania. Mechanizm błędu: kandydat ogłasza „mam O(log n) rozwiązanie", ale jednorazowy koszt sort() dominuje gdy wykonywane jest tylko jedno wyszukiwanie. Sortowanie + binsearch opłaca się gdy po jednym sortowaniu wykonujesz wiele wyszukiwań.
Warunki konieczne dla algorytmu
Kolekcja musi być posortowana według tego samego porządku którego używa porównanie z celem. Dla liczb zwykle rosnący; dla rekordów może to być wybrany klucz (np. id).
Drugim warunkiem jest szybki dostęp do elementu środkowego (O(1)). Tablica/lista indeksowana pozwala pobrać values[mid] w stałym czasie. Linked list wymaga przejścia od początku — niszczy to zaletę połowienia, bo dotarcie do mid to O(n), więc całość staje się O(n log n), gorsza niż liniowy O(n).
Trzeci warunek to monotoniczność porównania. Funkcja compare(item, target) musi zwracać konsekwentnie „mniejsze", „większe", „równe". Jeśli predykat jest niemonotoniczny, połowienie odrzuca część zawierającą odpowiedź.
records = [
{"id": 10, "name": "Ada"},
{"id": 20, "name": "Bob"},
{"id": 30, "name": "Cy"},
]
def find_by_id(items, target_id):
left = 0
right = len(items) - 1
while left <= right:
mid = (left + right) // 2
current_id = items[mid]["id"]
if current_id == target_id:
return items[mid]["name"]
if current_id < target_id:
left = mid + 1
else:
right = mid - 1
return None
print(find_by_id(records, 20)) # expected_output: Bob
print(find_by_id(records, 25)) # expected_output: None
Pułapka: linked list NIE obsługuje binary search efektywnie, bo nie ma dostępu losowego w O(1). Mechanizm błędu: dotarcie do mid wymaga przejścia O(n) po wskaźnikach. Sam fakt że struktura jest posortowana nie wystarcza do uzyskania O(log n) — potrzebujesz array-like indexing.
Implementacja — left, right, mid i warunki stopu
Klasyczna wersja używa przedziału domkniętego indeksów: left = 0, right = len(values) - 1, pętla trwa dopóki left <= right. Gdy left > right, zakres jest pusty i celu nie ma.
Pozycja mid dzieli aktualny zakres. Jeśli środek jest za mały, ustaw left = mid + 1; jeśli za duży, right = mid - 1. Dodanie/odjęcie jedynki usuwa sprawdzony element ze świeżego zakresu — bez tego pętla jest nieskończona, bo mid nie zmienia się.
Edge cases nie wymagają specjalnego algorytmu: pusta lista daje right = -1, więc pętla nie startuje; cel poza zakresem stopniowo opróżnia zakres. To jest siła konwencji [left, right] — nie potrzebujesz osobnych guardów.
def contains(values, target):
left = 0
right = len(values) - 1
while left <= right:
mid = (left + right) // 2
if values[mid] == target:
return True
if values[mid] < target:
left = mid + 1
else:
right = mid - 1
return False
print(contains([], 3)) # expected_output: False
print(contains([4, 8, 12], 2)) # expected_output: False
print(contains([4, 8, 12], 12)) # expected_output: True
Pułapka: najczęstszy błąd to pomieszanie konwencji. right = len(values) - 1 (przedział domknięty [left, right], pętla while left <= right, update right = mid - 1) vs right = len(values) (przedział prawostronnie otwarty [left, right), pętla while left < right, update right = mid). Mieszanie tych dwóch konwencji daje pętlę nieskończoną lub pominięcie elementu. Naprawa: trzymaj jedną konwencję od początku do końca.
Lower bound i upper bound
lower_bound(target) zwraca pierwszy indeks z elementem >= target — czyli pozycję, gdzie wstawić target zachowując porządek (z lewej strony duplikatów). upper_bound(target) zwraca pierwszy indeks z elementem > target — czyli pozycję za prawym brzegiem duplikatów.
Intuicja: dla unikalnych wartości oba zwracają sąsiednie pozycje. Różnica pojawia się tylko przy duplikatach, ale właśnie tam są najbardziej przydatne. upper_bound - lower_bound = count duplikatów — wzorzec do liczenia wystąpień bez przeglądania całej kolekcji.
W Pythonie bisect_left/bisect_right to gotowe implementacje:
from bisect import bisect_left, bisect_right
values = [1, 2, 2, 2, 5, 9]
left_edge = bisect_left(values, 2)
right_edge = bisect_right(values, 2)
print(left_edge) # expected_output: 1
print(right_edge) # expected_output: 4
print(right_edge - left_edge) # expected_output: 3
Własna implementacja granicy używa przedziału prawostronnie otwartego [left, right). Wtedy right = len(values), pętla while left < right, a right = mid zachowuje kandydata na odpowiedź:
def lower_bound(values, target):
left = 0
right = len(values)
while left < right:
mid = (left + right) // 2
if values[mid] < target:
left = mid + 1
else:
right = mid
return left
print(lower_bound([1, 2, 2, 2, 5], 2)) # expected_output: 1
print(lower_bound([1, 2, 2, 2, 5], 4)) # expected_output: 4
Pułapka: mylenie bisect_left i bisect_right przy duplikatach. Wejście [1, 2, 2, 2, 5] z target=2: bisect_left zwraca 1 (najwcześniejsza pozycja gdzie pasuje 2), bisect_right zwraca 4 (pierwsza pozycja za ostatnim 2). Mechanizm błędu: kandydat używa bisect_left do liczenia wystąpień, dostaje 1 zamiast 3. Naprawa: count = bisect_right - bisect_left.
Wzorzec dziel-i-zwyciężaj + find first true
Wyszukiwanie binarne to klasyczny przykład dziel-i-zwyciężaj: problem zostaje ograniczony do mniejszego podproblemu, decyzja wynika z własności porządku. Algorytm nie przeszukuje obu połówek — wybiera jedną. Tym różni się od merge sort (rozwiązuje oba podproblemy + scala) i quicksort (granicę tworzy partycjonowanie zamiast porównania).
Wzorzec „find first true" uogólnia binary search na predykaty monotoniczne. Predykat ma postać False, False, ..., True, True na uporządkowanej dziedzinie. Algorytm nie zna odpowiedzi z góry — używa monotoniczności żeby zawężać granicę między fałszem a prawdą. Klasyczne zastosowania: minimum capacity, minimum days, najmniejszy parametr spełniający warunek.
def first_true(left, right, predicate):
answer = right + 1 # sentinel — żaden element nie pasuje
while left <= right:
mid = (left + right) // 2
if predicate(mid):
answer = mid
right = mid - 1 # szukaj wcześniejszego True
else:
left = mid + 1
return answer
threshold = 17
print(first_true(0, 30, lambda x: x >= threshold)) # expected_output: 17
Pułapka: integer overflow w (left + right) // 2 w Pythonie nie występuje (integers nieograniczone), ale w C/Java może przekroczyć INT_MAX przy dużych wartościach. Bezpieczny wzorzec niezależny od języka: left + (right - left) // 2. Mechanizm błędu w C: dla left=2_000_000_000, right=2_000_000_000 suma przekracza 32-bit int, daje wynik ujemny. Na rozmowie warto pokazać świadomość, nawet pisząc w Pythonie.
Sygnały rozpoznawcze zadań na binary search
Zadanie pachnie binary search, gdy widzisz monotoniczność i potrzebę szybkiego znajdowania granicy. Sygnał → wzorzec:
"sorted array, find X" → binary_search (klasyczne)
"first occurrence / last → bisect_left / bisect_right
occurrence / count duplicates"
"find first index where condition → first_true (monotonic predicate)
becomes true"
"minimum capacity / minimum k → first_true on parametr
satisfying constraint"
"square root / integer division → binsearch on numeric range
without /"
"peak / mountain element → modified binary search
(locally)"
Sygnały odwrotne — kiedy binsearch NIE pasuje: dane nieposortowane bez możliwości zsortowania, linked list bez random access, predykat niemonotoniczny, problem wymaga znalezienia wszystkich wystąpień (binsearch znajduje granicę, nie listę).
patterns = {
"sorted lookup": "binary_search",
"first/last duplicate": "bisect_left / bisect_right",
"monotonic predicate": "first_true",
}
print(patterns["sorted lookup"]) # expected_output: binary_search
Kiedy NIE binary search
Binary search nie pasuje gdy nie masz monotoniczności. Konkretny anty-przykład: szukanie elementu w nieposortowanej tablicy. Próba binsearch zwróci nieprzewidywalny wynik, bo decyzja „idź lewo czy prawo" nie ma podstaw — środkowy element nie mówi nic o tym, gdzie jest cel. Tu pasuje hash set (O(1) lookup po O(n) setup) — szczegóły: Haszowanie w Zadaniach.
Drugi anty-przykład: dynamiczna kolekcja z częstymi insertami. Każdy insert do sorted array kosztuje O(n) (przesunięcie elementów), więc n insertów to O(n²). Tu pasuje BST lub heap — struktury które utrzymują porządek przy wstawianiu w O(log n).
import bisect
# anti-example 1: lookup w nieposortowanym → hash set
seen = {2, 4, 7, 9, 13}
print(9 in seen) # expected_output: True
# anti-example 2: znajdowanie wszystkich wystąpień przez bisect
values = [1, 2, 2, 2, 5]
left = bisect.bisect_left(values, 2)
right = bisect.bisect_right(values, 2)
print(values[left:right]) # expected_output: [2, 2, 2]
Najczęstsze błędy
Brak sortowania. Binsearch na nieposortowanej tablicy zwraca losowy indeks lub -1 — algorytm zakłada że values[mid] < target implikuje „cel po prawej". Bez monotoniczności decyzja jest losowa. Naprawa: sort() przed pierwszym wywołaniem; akceptuj O(n log n) setup gdy planujesz wiele wyszukiwań.
Off-by-one w right. Mieszanie konwencji right = len-1 ([left, right]) i right = len ([left, right)) daje pętlę nieskończoną lub pominięty element. Naprawa: wybierz jedną konwencję i trzymaj się jej; [left, right] z while left <= right jest najczęstsza i najbezpieczniejsza dla początkujących.
Brak +1/-1 w update zakresu. left = mid zamiast left = mid + 1 powoduje pętlę nieskończoną gdy values[mid] != target — mid nie zmienia się przy następnej iteracji. Naprawa: zawsze przesuwaj zakres o 1, żeby usunąć właśnie sprawdzony element.
bisect_left zamiast bisect_right (lub odwrotnie). Dla [1, 2, 2, 2, 5] z target=2: bisect_left daje 1 (lewy brzeg), bisect_right daje 4 (prawy brzeg). Naprawa: do liczby wystąpień używaj bisect_right - bisect_left; do wstawienia z lewej — bisect_left; do wstawienia z prawej — bisect_right.
Linked list jako struktura wejściowa. Brak O(1) random access niszczy ideę połowienia — dotarcie do mid to O(n), więc całość staje się O(n log n), gorsza niż liniowy O(n). Naprawa: konwertuj do array (list(linked_list)) jeśli planujesz wiele wyszukiwań, albo wybierz inną strukturę (BST, hash set).
FAQ
Czy mogę zrobić binary search po liście obiektów z custom comparatorem?
Tak, ale bisect w Pythonie nie wspiera custom comparator wprost. Dwa podejścia: (1) bisect_left(values, target, key=lambda x: x.id) — od Pythona 3.10 key parametr jest dostępny; (2) zbuduj listę kluczy keys = [item.id for item in values] i użyj bisect_left(keys, target_id) — działa w każdej wersji ale dubluje pamięć.
Jak binsearch radzi sobie z floating point?
Z floats nie używasz == w warunku values[mid] == target (rzadko trafiasz dokładnie). Zamiast tego konwergujesz do przedziału: while right - left > epsilon: mid = (left + right) / 2; if predicate(mid): right = mid else: left = mid. To jest binary search na continuous range, nie na indeksach. Klasyczne dla square root, integer division, monotonic continuous functions.
Skąd (left + right) // 2 może powodować overflow?
W C/Java int ma 32-bit limit (~2 mld). Dla left=high=2_000_000_000 suma 4 mld przekracza zakres → wraps do liczby ujemnej → mid jest ujemny → indexing fails. Bezpieczny wzorzec: left + (right - left) // 2 — różnica dwóch dodatnich nigdy nie przekroczy ich maksimum. W Pythonie integers są nieograniczone, więc problem nie występuje, ale konwencja low + (high - low) // 2 jest standardem branżowym.
Czy binsearch działa na rotated sorted array?
Tak, ale wymaga modyfikacji. Klasyczny problem rekrutacyjny: tablica [4, 5, 6, 1, 2, 3] (rotacja). Standardowy binsearch nie działa, bo values[mid] nie pozwala odrzucić jednoznacznie połowy. Rozwiązanie: porównuj values[mid] z values[left] lub values[right] żeby wykryć która połowa jest sorted, potem zdecyduj gdzie szukać. Złożoność wciąż O(log n).
Co z duplikatami? Czy binsearch zwraca losowy z wystąpień?
Standardowy binary_search (z == check) zwraca dowolne wystąpienie — może być pierwsze, może ostatnie, może środkowe, zależy od kolejności porównań. Jeśli potrzebujesz konkretnego (pierwszego/ostatniego), użyj bisect_left/bisect_right. Jeśli implementujesz custom find-first/find-last, wzorzec to find_first_true z odpowiednim predykatem (values[mid] >= target dla pierwszego).
Czy bisect.insort jest szybkie?
bisect.insort(list, value) znajduje pozycję w O(log n) (binsearch), ale wstawienie do listy to O(n) (przesunięcie elementów). Łączny koszt to O(n), nie O(log n). Dla częstych insertów w sorted collection wybierz BST (O(log n) dla balansowanego), heap (O(log n) dla insert do priority queue) albo SortedList z biblioteki sortedcontainers.
Powiązane tematy
- Big O w 10 Minut — Notacja Złożoności — kontekst dla
O(log n)jako klasy wzrostu; tam są inne klasy i sygnały rozpoznawcze. - Drzewa Binarne — Wzorzec Rekurencyjny — BST używa tej samej idei „halve the search space" na strukturze wskaźnikowej zamiast tablicy.
- Algorytmy Sortowania —
O(n log n)koszt setup'u przed binsearch; merge sort, quicksort, Timsort jako warunek pre-sort.
Sprawdź swoją wiedzę quizem
Przerób ten artykuł w 15-pytaniowy quiz testujący O(log n), warunki konieczne, off-by-one, lower/upper bound i find first true: https://odpytywarka.pl/q/ydh8MN.
Masz własne notatki na rozmowę? Wgraj PDF lub wklej tekst na stworz-quiz-z-pdf — pierwsze 3 strony PDF i 15 pytań jednokrotnego wyboru za darmo, generowanie 30-60 sekund.
Źródła
- Binary search algorithm — Wikipedia
- Python
bisectmodule — implementacja lower/upper bound - Wyszukiwanie binarne — Wikipedia (polska)
- Python Wiki — TimeComplexity — koszty operacji na list