Wyszukiwanie binarne — połowienie na tablicy

🎯 Po co Ci to?

W dziale 1 zgadywałeś liczbę z zakresu 1–100 w siedem pytań, w 2.7 policzyłeś, że miliard możliwości pada po trzydziestu. Dziś ta zgadywanka dostaje pracę na etacie: wyszukiwanie binarne to połowienie zastosowane do posortowanej listy — algorytm, który w miliardowej bazie znajduje rekord w 30 krokach i który (obok haszowania) odpowiada za to, że internet w ogóle nadąża. Jest też drugim bohaterem tej jednostki: przykładem, jak łatwo zepsuć prosty pomysł. Legendarna analiza z lat 80. wykazała, że większość zawodowych programistów pisze binarne z błędem. Ty nie będziesz większością.

✅ Czego się nauczysz

Po tej jednostce potrafisz:

wykonać wyszukiwanie binarne na kartce, zapisując przedział poszukiwań;
wyjaśnić, czemu wymaga posortowanej listy i skąd bierze się koszt $\log_2 n$;
(w rozszerzeniu) zapisać je w kodzie i ominąć klasyczne pułapki granic przedziału.

🔁 Przypomnij sobie

Z 1.4: każde pytanie połowiące odrzuca połowę kandydatów; z 2.7: $\log_2 n$ pytań wystarcza; z 3.4: porządek słownikowy — binarne działa i na napisach.

📘 Wyjaśnienie

Pomysł. Lista jest posortowana rosnąco. Szukasz $x$. Zajrzyj do środka: jeśli element środkowy to $x$ — wygrana; jeśli jest mniejszy od $x$, to $x$ może być tylko w prawej połowie (lewa cała jest jeszcze mniejsza — to tu pracuje porządek!); jeśli większy — tylko w lewej. Jednym porównaniem odrzucasz połowę listy. Powtarzaj na pozostałej połowie, aż znajdziesz — albo aż przedział się wyczerpie.

Wyszukiwanie binarne liczby 23 na posortowanej tablicy: kolejne kroki zawężają przedział — środek 15 za mały, środek 31 za duży, środek 23 trafiony; po każdym pytaniu połowa tablicy szarzeje. · rys. własny

Koszt znasz z rachunku w 2.7: po $k$ pytaniach zostaje $n/2^k$ kandydatów, więc pytań jest co najwyżej $\lceil \log_2 n \rceil$ — dla miliona 20, dla miliarda 30. Tabela w bibliotece z zadania 2.7/3 przestaje być ciekawostką: bibliotekarka wykonywała wyszukiwanie binarne.

Warunek istnienia: porządek. Binarne na liście nieposortowanej nie jest „trochę gorsze" — jest bezsensowne: wnioskowanie „środek za mały ⇒ $x$ na prawo" stoi w całości na posortowaniu. To najczęstszy błąd koncepcyjny na sprawdzianach: stosowanie binarnego tam, gdzie porządku nie ma. Stąd ekonomia tego działu: sortowanie (6.3–6.7) to inwestycja, binarne — dywidenda z niej przy każdym szukaniu.

💭 Pomyśl: Masz posortowaną listę 1024 nazwisk i wykonasz na niej tylko jedno wyszukiwanie. Czy opłaca się jej posortowanie, gdyby nie była posortowana? A gdy wyszukiwań będzie tysiąc?

Sprawdź odpowiedź

Jedno szukanie: liniowe kosztuje ~1024 porównania bez żadnych przygotowań; sortowanie samo kosztuje więcej (najlepsze algorytmy ~$n \log n \approx 10,000$) — nie opłaca się. Tysiąc szukań: liniowo ~$1000 \cdot 512$ (średnio) $= 512,000$; z sortowaniem: $10,000 + 1000 \cdot 10 = 20,000$ — dwudziestopięciokrotna wygrana. Formuła decyzji: porządek się zwraca, gdy (koszt sortowania) < (liczba szukań) × (oszczędność na szukaniu). Inwestycja i dywidenda, dosłownie.

[R] Kod — i jego słynne miny. Przedział poszukiwań trzymamy w dwóch indeksach lewy, prawy (włącznie):

def binarne(L, x):
    lewy, prawy = 0, len(L) - 1
    while lewy <= prawy:               # przedział niepusty
        srodek = (lewy + prawy) // 2
        if L[srodek] == x:
            return srodek
        if L[srodek] < x:
            lewy = srodek + 1          # x tylko na prawo od środka
        else:
            prawy = srodek - 1         # x tylko na lewo
    return -1

Cztery miejsca, w których saperzy ginęli:

lewy <= prawy, nie < — przedział jednoelementowy (lewy == prawy) to wciąż legalny kandydat; z ostrym < algorytm nie sprawdzi ostatniego podejrzanego i skłamie „nie ma" dla elementów na brzegach.
srodek + 1 / srodek - 1, nie gołe srodek — środek już sprawdziliśmy; zostawisz go w przedziale, a pętla przy dwóch elementach zapętli się na wieki (przedział przestaje maleć — pętla nieskończona z 3.3 w nowym przebraniu).
(lewy + prawy) // 2 — dzielenie całkowite; w Pythonie suma nie przepełni się nigdy, ale w językach o stałych bitach (2.3!) lewy + prawy potrafiło przekroczyć zakres — ten dokładnie błąd siedział latami w bibliotece standardowej Javy. Zapis odporny: lewy + (prawy - lewy) // 2.
Poprawność pilnowana niezmiennikiem: przez cały czas „jeśli $x$ jest na liście, to jest w przedziale $[lewy, prawy]$". Każda gałąź musi go utrzymywać — to zdanie jest szkieletem uzasadnienia poprawności na maturze.

🧮 Prześledź

binarne([2, 5, 8, 12, 16, 23, 38, 56, 72, 91], 23) — uzupełnij:

krok	`lewy`	`prawy`	`srodek`	`L[srodek]`	decyzja
1	0	9	?	?	?
2	?	?	?	?	?
3	?	?	?	?	?

Sprawdź odpowiedź

Krok 1: środek $(0+9)//2 = 4$, $L[4] = 16 < 23$ → lewy = 5. Krok 2: $(5+9)//2 = 7$, $L[7] = 56 > 23$ → prawy = 6. Krok 3: $(5+6)//2 = 5$, $L[5] = 23$ — trafiony, indeks 5. Trzy porównania na dziesięciu elementach ($\lceil \log_2 10 \rceil = 4$ to górna granica). Prześledź jeszcze $x = 3$ (którego nie ma): przedział skurczy się do pustego (lewy > prawy) w 3 krokach — brak elementu kosztuje tyle samo co trafienie, inaczej niż w liniowym.

⚠️ Uwaga, pułapka

Binarne bywa stosowane do rzeczy, które nie wyglądają jak lista — i to jest jego druga kariera: szukanie progu. „Od jakiego roku produkcji auto spala poniżej 5 l?", „przy jakiej dawce lek zaczyna działać?", „która wersja programu zepsuła testy?" — jeśli własność jest monotoniczna (od pewnego miejsca już zawsze tak), połowienie znajduje próg w logarytmicznie wielu próbach. Narzędzia programistów mają wbudowaną komendę szukającą zepsutej wersji dokładnie tak (połowienie historii zmian). Warunkiem — jak zawsze — monotoniczność: „posortowanie" świata, nie tablicy.

🛠️ Teraz Ty

Bez komputera: rozegraj binarne na kartce dla listy 15 kolejnych nazwisk z dziennika (posortowanych!) — znajdź swoje w ≤ 4 pytaniach. [R] Z komputerem: zaimplementuj binarne, przetestuj na brzegach (pierwszy, ostatni, brak — mniejszy od wszystkich i większy od wszystkich, lista pusta, jednoelementowa), a potem celowo wstaw błąd lewy = srodek i znajdź dane, na których program wisi.

📐 Definicje tej lekcji

Wyszukiwanie binarne — połowienie przedziału na posortowanej liście; koszt $\lceil \log_2 n \rceil$ porównań.
[R] Niezmiennik przedziału — „jeśli $x$ jest, to w $[lewy, prawy]$"; każda gałąź musi go utrzymać, pętla — zmniejszać przedział.

📌 Najważniejsze w pigułce

Jedno porównanie = połowa listy w koszu; milion → 20 kroków, miliard → 30.
Bez posortowania binarne nie jest wolniejsze — jest bez sensu.
[R] Miny: <= w warunku, ±1 przy zawężaniu, dzielenie całkowite; pilnuj niezmiennika.

🎒 Zadania

Ile porównań (maksymalnie) wykona binarne na liście: (a) 100, (b) 10 000, (c) $10^9$ elementów? Dla (c) porównaj z liniowym — ile razy szybciej?

Wskazówka i odpowiedź

(a) $\lceil \log_2 100 \rceil = 7$; (b) 14; (c) 30. Liniowe na miliardzie: do $10^9$ porównań — binarne jest ~33 miliony razy szybsze. I kluczowa obserwacja skali: przejście z (a) do (c) to dane większe dziesięć milionów razy, a koszt wzrósł z 7 do 30 — logarytm niemal nie zauważa wzrostu świata.

Lista posortowana malejąco. Co trzeba zmienić w algorytmie? A co się stanie, jeśli o tym zapomnisz — skłamie zawsze, czasem, nigdy?

Wskazówka i odpowiedź

Wystarczy odwrócić decyzje: L[srodek] < x → szukaj w lewo (większe są z lewej). Bez poprawki algorytm kłamie czasem: bywa, że przypadkiem trafi (np. $x$ akurat w pierwszym środku), zwykle jednak zawęża w złą stronę i mówi „nie ma" o elemencie, który jest. Błędy „czasem" są gorsze od „zawsze" — przechodzą połowę testów. Nawyk: pierwsze pytanie przy binarnym brzmi „w którą stronę rośnie?".

[R] Zmodyfikuj binarne, by zwracało pozycję wstawienia: indeks, pod którym $x$ powinien się znaleźć, żeby porządek przetrwał (dla [2,5,8], $x=6$ → 2). Po czym poznasz, że Twoja wersja jest poprawna na brzegach?

Wskazówka i odpowiedź

Usuń przypadek „trafiony" (albo zwracaj środek), a po pętli zwróć lewy — po wyczerpaniu przedziału lewy wskazuje dokładnie pierwsze miejsce, gdzie element większy-lub-równy powinien stać. Brzegi do sprawdzenia: $x$ mniejszy od wszystkich → 0; większy → len(L); równy istniejącemu → pozycja tego istniejącego (lub tuż za — zależnie od wariantu; specyfikacja musi wybrać). Ta funkcja to pomost do 6.4: sortowanie przez wstawianie z binarnym szukaniem miejsca.

🔍 Sprawdź, czy umiesz

Rozegrać binarne na kartce z jawnym przedziałem i policzyć pytania.
Uzasadnić koszt logarytmem i warunek posortowania — na czym dokładnie stoi wnioskowanie?
[R] Wskazać w cudzym kodzie miny granic przedziału i poprawić je.

Ucz się tej jednostki z asystentem