Binarne wyszukiwanie — jak znaleźć coś szybciej niż inni

Po co się tego uczymy?

Każde wyszukiwanie w Google, YouTube czy Spotify opiera się na binarnej logice podziału — zrozumienie, DLACZEGO dzielenie zakresu na pół jest tak potężne, to jeden z najważniejszych "aha momentów" w nauce algorytmiki, wymagany na maturze rozszerzonej.

Teoria

Wyszukiwanie binarne ("binarny" = podwójny) to sposób znajdowania elementu przez CIĄGŁE DZIELENIE zakresu na pół. Zamiast przeglądać wszystko po kolei, sprawdzasz ŚRODEK — i od razu wyrzucasz połowę danych. To jak gra "zgadnij liczbę od 1 do 100": po zaledwie 7 pytaniach zawsze znajdziesz szukaną liczbę (bo 2⁷ ≈ 128).

Warunek konieczny: dane muszą być POSORTOWANE (np. rosnąco) — bez tego algorytm nie zadziała poprawnie.

Kroki algorytmu: (1) wybierz środkowy element tablicy, (2) jeśli to szukana wartość → koniec, (3) jeśli szukana wartość jest MNIEJSZA → szukaj w LEWEJ połowie, (4) jeśli WIĘKSZA → szukaj w PRAWEJ połowie, (5) powtarzaj, aż znajdziesz lub skończy się lista.

Porównanie szybkości — dlaczego to takie ważne:

Liczba elementów	Wyszukiwanie liniowe	Wyszukiwanie binarne
10	do 10 porównań	do 4 porównań
100	do 100 porównań	do 7 porównań
1 000	do 1 000 porównań	do 10 porównań
1 000 000	do 1 000 000 porównań	tylko 20 porównań

To różnica między MINUTĄ a UŁAMKIEM SEKUNDY! Każdy krok eliminuje połowę danych — po 20 krokach z miliona elementów zostaje tylko 1. Złożoność obliczeniowa wyszukiwania binarnego to O(log₂ n) (logarytmiczna) — dramatycznie szybsza niż O(n) wyszukiwania liniowego.

Wady i ograniczenia: działa TYLKO na posortowanych listach (nieuporządkowane dane dadzą błędny wynik), nie nadaje się, gdy dane często się zmieniają (trzeba by je sortować od nowa za każdym razem).

Zastosowania: bazy danych (indeksowanie rekordów), wyszukiwarki internetowe, systemy plików, gry (szybkie sprawdzanie kolizji lub punktów na mapie).

Schemat

Szukamy liczby 42 w: [5, 12, 18, 23, 34, 42, 57, 64]

Krok 1: środek = 23        42 > 23 → szukaj w PRAWEJ połowie
        [34, 42, 57, 64]
             ↑
Krok 2: środek = 42        Trafione! (2 kroki zamiast 8)

Porównanie: 1 000 000 elementów
  1000000 → 500000 → 250000 → 125000 → ... → 1   (tylko 20 kroków!)

Przykład z życia

Gra "zgadnij liczbę od 1 do 100": pytasz "czy to 50?", jeśli za duża — szukasz od 1 do 49, jeśli za mała — od 51 do 100, i sprawdzasz środek nowego zakresu. Dokładnie tę samą strategię komputer stosuje przy przeszukiwaniu ogromnych, posortowanych zbiorów danych — np. numerów telefonów w książce telefonicznej.

wyszukiwanie_binarne.py

# Wyszukiwanie liniowe (dla porównania) - sprawdza KAŻDY element po kolei
def wyszukiwanie_liniowe(lista, x):
    for i in range(len(lista)):
        if lista[i] == x:
            return i
    return -1


# Wyszukiwanie binarne - wersja iteracyjna
def wyszukiwanie_binarne(lista, x):
    lewy = 0
    prawy = len(lista) - 1

    while lewy <= prawy:
        srodek = (lewy + prawy) // 2
        if lista[srodek] == x:
            return srodek
        elif lista[srodek] < x:
            lewy = srodek + 1
        else:
            prawy = srodek - 1

    return -1


dane = [5, 12, 18, 23, 34, 42, 57, 64]
print(wyszukiwanie_binarne(dane, 42))
# Wynik: 5  (bo 42 znajduje się na pozycji 5)

wyszukiwanie_binarne_rekurencyjne.py

# Wersja rekurencyjna (dla chętnych)
def wyszukiwanie_binarne_rek(lista, x, lewy, prawy):
    if lewy > prawy:
        return -1
    srodek = (lewy + prawy) // 2
    if lista[srodek] == x:
        return srodek
    elif lista[srodek] < x:
        return wyszukiwanie_binarne_rek(lista, x, srodek + 1, prawy)
    else:
        return wyszukiwanie_binarne_rek(lista, x, lewy, srodek - 1)

dane = [5, 12, 18, 23, 34, 42, 57, 64]
print(wyszukiwanie_binarne_rek(dane, 23, 0, len(dane) - 1))

Komentarz i wyjaśnienie kodu

W wersji iteracyjnej dwie zmienne lewy i prawy wyznaczają AKTUALNIE przeszukiwany fragment listy — po każdej nietrafionej próbie jedna z nich się zmienia, ZAWĘŻAJĄC zakres o połowę. Pętla while lewy <= prawy kończy się, gdy zakres "zniknie" (element nie istnieje w liście).

Wersja rekurencyjna robi DOKŁADNIE to samo, ale zamiast pętli while wywołuje SAMĄ SIEBIE z nowym, węższym zakresem (lewy/prawy jako parametry) — warunek if lewy > prawy: return -1 to warunek stopu rekurencji.

Ćwiczenie samodzielne

Uruchom obie wersje wyszukiwania binarnego dla różnych wartości z listy [5, 12, 18, 23, 34, 42, 57, 64] i policz ręcznie, ile kroków (porównań) zajmuje znalezienie każdej z nich.

Zadania do pracy własnej

Napisz program, który tworzy listę liczb 1-100 i wyszukuje liczbę podaną przez użytkownika metodą binarną. Wyświetl liczbę kroków, jakie zajęło jej znalezienie.
Załaduj listę 100 elementów i porównaj, ile kroków potrzebuje wyszukiwanie liniowe, a ile binarne dla tej samej wartości. Które jest szybsze i o ile?
Użyj posortowanej listy imion ["Adam", "Bartek", "Ewa", "Kasia", "Marta", "Zosia"] i znajdź imię wpisane przez użytkownika metodą binarną (porównując napisy zamiast liczb). Dodatkowo: przerób wersję rekurencyjną tak, żeby w każdym kroku wypisywała sprawdzany zakres (początek i koniec) — zobacz, jak zakres się kurczy.

Typowe błędy

Użycie wyszukiwania binarnego na NIEPOSORTOWANEJ liście — algorytm da BŁĘDNY wynik (albo nie znajdzie istniejącego elementu), bo cała jego logika opiera się na założeniu, że dane są uporządkowane.

Błąd "o jeden" przy ustalaniu lewy/prawy po nietrafionym porównaniu — po sprawdzeniu środka trzeba przesunąć granicę o srodek + 1 albo srodek - 1 (NIE samo srodek), inaczej pętla może się zapętlić w nieskończoność albo pominąć element.

Zapominanie o warunku stopu w wersji rekurencyjnej (if lewy > prawy) — bez niego rekurencja nigdy się nie zakończy dla nieistniejącego elementu.

Nawiązanie do egzaminu zawodowego

Wyszukiwanie binarne to klasyczny przykład algorytmu o złożoności logarytmicznej O(log n) — bezpośrednio powiązany z tematem złożoności obliczeniowej (ostatnia lekcja tego działu) oraz metodą połowienia/bisekcji (kolejna lekcja), która stosuje identyczną strategię "dziel na pół" do zupełnie innego problemu — szukania miejsc zerowych funkcji.