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

1. Wstęp – czyli co to znaczy „binarne”?

Słowo „binarne” pochodzi od łacińskiego binarius – czyli „podwójny”, „dwa na raz”.
Wyszukiwanie binarne 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 w „zgadnij liczbę od 1 do 100”, tylko w wersji komputerowej.

2. Przykład z życia – zgadnij liczbę

Załóżmy, że myślisz o liczbie od 1 do 100, a ja próbuję ją odgadnąć:

• pytam: „Czy to 50?”
  – jeśli powiesz „za duża”, to wiem, że szukam od 1 do 49.
  – jeśli powiesz „za mała”, to szukam od 51 do 100.
• potem sprawdzam środek nowego zakresu (np. 25 albo 75).

Za każdym razem połowa możliwości znika.
Po zaledwie 7 pytaniach zawsze znajdę Twoją liczbę (bo 2⁷ ≈ 128).

To właśnie wyszukiwanie binarne.

3. Zasada działania

Wyszukiwanie binarne działa tylko wtedy, gdy dane są uporządkowane (np. rosnąco).

Kroki:

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.

4. Przykład krok po kroku

Szukamy liczby 23 w posortowanej liście:

[5, 12, 18, 23, 34, 42, 57, 64]

1. Środek → 23 (na pozycji 4)
   bingo! znalezione od razu.

Inny przykład: szukamy 42

1. Środek → 23 → 42 > 23, więc szukamy w prawej połowie [34, 42, 57, 64]
2. Środek → 42 → znalezione.

Wystarczyły 2 kroki zamiast 8!

5. Wyszukiwanie liniowe (dla porównania)

def wyszukiwanie_liniowe(lista, x):
    for i in range(len(lista)):
        if lista[i] == x:
            return i
    return -1

def wyszukiwanie_liniowe(lista, x):
    for i in range(len(lista)):
        if lista[i] == x:
            return i
    return -1

To prosty sposób, ale trzeba przejrzeć każdy element.
Jeśli lista ma milion pozycji – to milion porównań.

6. Wersja binarna – szybka i elegancka

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

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

Przykład:

dane = [5, 12, 18, 23, 34, 42, 57, 64]
print(wyszukiwanie_binarne(dane, 42))

dane = [5, 12, 18, 23, 34, 42, 57, 64]
print(wyszukiwanie_binarne(dane, 42))

Wynik:

5

5

(bo 42 znajduje się na pozycji 5)

7. 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))

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))

8. Porównanie szybkości

To różnica między minutą a ułamkiem sekundy!
Dlatego każde wyszukiwanie w Google, YouTube czy Spotify opiera się na binarnej logice podziału.

9. Intuicja – dlaczego to takie szybkie

Każdy krok eliminuje połowę danych.
Zostaje połowa, potem połowa z połowy, potem połowa z tej połowy…

Przy 1 000 000 elementów:

1000000 → 500000 → 250000 → 125000 → ...

Po 20 krokach zostaje tylko 1 element.
Złożoność obliczeniowa to O(log₂ n).

10. Wady i ograniczenia

• działa tylko na posortowanych listach,
• jeśli dane są nieuporządkowane – wyniki będą błędne,
• nie nadaje się, gdy dane często się zmieniają (bo trzeba je sortować od nowa).

11. Gdzie się to stosuje

• w bazach danych (np. indeksowanie rekordów),
• w wyszukiwarkach internetowych,
• w systemach plików,
• w grach (np. szybkie sprawdzanie kolizji lub punktów na mapie).

12. Zadania dla ucznia

Zadanie 1 – Szukaj liczby
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.

Zadanie 2 – Porównaj metody
Załaduj listę 100 elementów.
Porównaj, ile kroków potrzebuje wyszukiwanie liniowe i binarne.
Które jest szybsze?

Zadanie 3 – Wersja tekstowa
Użyj listy imion:

imiona = ["Adam", "Bartek", "Ewa", "Kasia", "Marta", "Zosia"]

imiona = ["Adam", "Bartek", "Ewa", "Kasia", "Marta", "Zosia"]

Znajdź imię wpisane przez użytkownika.
Pamiętaj, żeby lista była posortowana.

Zadanie 4 – Dla chętnych
Przerób wersję rekurencyjną tak, żeby w każdym kroku wypisywała sprawdzany zakres (początek i koniec).
Zobacz, jak zakres się kurczy.

13. Podsumowanie

14. Do zapamiętania

Wyszukiwanie binarne to sztuka odrzucania tego, co niepotrzebne.
Nie szukaj wszędzie – skup się tylko na połowie, która ma sens.

15. Dla wzrokowców

[  5, 12, 18, 23, 34, 42, 57, 64 ]
          ↑
Szukam 42
→ 42 > 23 → szukam w prawej połowie

[ 34, 42, 57, 64 ]
     ↑
Trafione!