Wyszukiwanie binarne - rekurencyjne i iteracyjne

1. Czym jest wyszukiwanie binarne?

Wyszukiwanie binarne (binary search) to efektywny algorytm wyszukiwania w posortowanej liście.

Idea – "zgadywanka liczb":

Zgadnij liczbę od 1 do 100:

Próba 1: 50 → "Za mało"
Próba 2: 75 → "Za dużo"
Próba 3: 62 → "Za mało"
Próba 4: 68 → "Za dużo"
Próba 5: 65 → "Zgadłeś!"

Tylko 5 prób dla 100 liczb!

Strategia:

  1. Sprawdź środkowy element
  2. Jeśli równy – znaleziono!
  3. Jeśli szukany mniejszy → szukaj w lewej połowie
  4. Jeśli szukany większy → szukaj w prawej połowie
  5. Powtarzaj

2. Wizualizacja

Szukamy: 22 w [3, 9, 10, 27, 38, 43, 82]

Krok 1: [3, 9, 10, 27, 38, 43, 82]
                  ↑ środek = 27
        22 < 27 → szukaj w lewej połowie

Krok 2: [3, 9, 10, 27, 38, 43, 82]
            ↑ środek = 9
        22 > 9 → szukaj w prawej połowie

Krok 3: [3, 9, 10, 27, 38, 43, 82]
                ↑ środek = 10
        22 > 10 → szukaj w prawej połowie

Krok 4: [3, 9, 10, 27, 38, 43, 82]
                  ↑ tylko 27 pozostało
        22 ≠ 27 → NIE ZNALEZIONO

Tylko 4 porównania zamiast 7 (liniowe)!

3. Implementacja iteracyjna

Dlaczego left + (right - left) // 2?

W Pythonie to nie problem (dowolnie duże liczby), ale dobra praktyka!

4. Implementacja rekurencyjna

5. Wizualizacja z debugiem

Wynik:

Szukam: 27 w [3, 9, 10, 27, 38, 43, 82]

Iteracja 1:
  Zakres: arr[0:7] = [3, 9, 10, 27, 38, 43, 82]
  Środek: arr[3] = 27
  ✅ ZNALEZIONO na indeksie 3!

6. Złożoność czasowa: O(log n) ✅

Analiza:

Każda iteracja dzieli listę na pół:
n → n/2 → n/4 → n/8 → ... → 1

Liczba kroków = log₂(n)

Przykłady:

n (rozmiar) Kroki (log₂ n) Liniowe (n) Różnica
10 4 10 2.5x
100 7 100 14x
1,000 10 1,000 100x
1,000,000 20 1,000,000 50,000x

Dramatyczna różnica dla dużych danych!

7. Złożoność pamięciowa

Iteracyjne: O(1)

Rekurencyjne: O(log n)

Iteracyjne lepsze pod względem pamięci!

8. Porównanie: iteracyjne vs rekurencyjne

Wniosek: Iteracyjne nieznacznie szybsze (brak overhead rekurencji).

9. Wyszukiwanie pierwszego/ostatniego wystąpienia

Dla duplikatów – znajdź pierwsze lub ostatnie wystąpienie:

9.1. Pierwsze wystąpienie

9.2. Ostatnie wystąpienie

10. Zliczanie wystąpień

Złożoność: O(log n) – znacznie lepsze niż liniowe O(n)!

11. Moduł bisect w Pythonie

Python ma wbudowany moduł do wyszukiwania binarnego:

Różnica: bisect_left vs bisect_right

12. Wyszukiwanie zakresu wartości

Zastosowanie: LeetCode problem "Find First and Last Position of Element in Sorted Array"

13. Wyszukiwanie w rotowanej liście

Lista posortowana, ale rotowana:

14. Wyszukiwanie w nieskończonej liście

Złożoność: O(log n) nawet dla nieskończonej listy!

15. Benchmark

16. Podsumowanie

Wyszukiwanie binarne:

  • Złożoność czasowa: O(log n) ✅
  • Złożoność pamięciowa: O(1) iteracyjne, O(log n) rekurencyjne
  • WYMAGANE: Lista posortowana ❗
  • Prostota: Średnio złożone

Zalety: - Bardzo szybkie – O(log n) - Iteracyjne: O(1) pamięci - Przewidywalna wydajność

Wady: - Wymaga posortowania (kosztowne dla nieposortowanych) - Bardziej złożone niż liniowe

Iteracyjne vs Rekurencyjne:

Aspekt Iteracyjne Rekurencyjne
Pamięć O(1) ✅ O(log n)
Szybkość Nieznacznie ✅ Wolniejsze
Prostota Podobna Podobna
Elegancja - ✅ Elegancksze

Rekomendacja: Używaj iteracyjnego w praktyce (O(1) pamięci, szybsze).

Kiedy używać: - ✅ Posortowane dane - ✅ Wielokrotne wyszukiwania (sortuj raz, potem O(log n)) - ✅ Duże dane (n > 100)

Kiedy NIE używać: - ❌ Nieposortowane + jednorazowe (koszt sortowania > liniowe) - ❌ Małe dane (n < 20) – różnica nieznaczna

Porównanie:

n = 1,000,000:
- Liniowe: ~500,000 porównań średnio
- Binarne: ~20 porównań
- 25,000x szybsze!

Co dalej warto poznać:

  • Wyszukiwanie interpolacyjne (lepsze dla równomiernego rozkładu)
  • Jump search, exponential search
  • Ternary search (dla funkcji unimodalnych)
  • Binary search na odpowiedzi (technika w algorytmach)
Wróć do spisu lekcji