Wyszukiwanie interpolacyjne

1. Czym jest wyszukiwanie interpolacyjne?

Wyszukiwanie interpolacyjne (interpolation search) to ulepszona wersja wyszukiwania binarnego, która działa lepiej dla równomiernie rozłożonych danych.

Kluczowa różnica:

Wyszukiwanie binarne: - Zawsze sprawdza środek listy - Nie wykorzystuje wartości elementów

Wyszukiwanie interpolacyjne: - Sprawdza szacowaną pozycję na podstawie wartości - Wykorzystuje interpolację liniową

Analogia – książka telefoniczna:

Szukasz nazwiska "Kowalski" w książce telefonicznej:

❌ Binarne: Zawsze otwórz na środku
   (nieefektywne – "K" jest bliżej środka niż "A")

✅ Interpolacyjne: Otwórz około 1/2 książki
   (inteligentne – "K" jest w środku alfabetu)

2. Wizualizacja

Wyszukiwanie binarne vs interpolacyjne:

Lista: [10, 20, 30, 40, 50, 60, 70, 80, 90]
Szukamy: 20

BINARNE:
Krok 1: [10, 20, 30, 40, 50, 60, 70, 80, 90]
                        ↑ środek = 50
        20 < 50 → lewo
Krok 2: [10, 20, 30, 40, 50, ...]
            ↑ środek = 20
        ZNALEZIONO!

INTERPOLACYJNE:
Krok 1: [10, 20, 30, 40, 50, 60, 70, 80, 90]
         ↑ pozycja szacowana ≈ 1 (blisko początku)
            arr[1] = 20
        ZNALEZIONO w 1 kroku!

3. Wzór na pozycję

Intuicja wzoru:

Dla listy [10, 90] szukamy 50:

Proporcja: (50 - 10) / (90 - 10) = 40/80 = 0.5 (50%)

Pozycja: 0 + 0.5 * (7 - 0) ≈ 3.5 → 3

4. Implementacja iteracyjna

5. Wizualizacja z debugiem

Wynik:

Szukam: 50 w [10, 20, 30, 40, 50, 60, 70, 80, 90]

Iteracja 1:
  Zakres: arr[0:9] = [10, 20, 30, 40, 50, 60, 70, 80, 90]
  Wartości: [10, 90]
  Interpolacja: pos = 0 + ((50-10) * 8) / (90-10) = 4
  Sprawdzam: arr[4] = 50
  ✅ ZNALEZIONO!

6. Złożoność czasowa

Najlepszy przypadek: O(1)

Element na szacowanej pozycji:

Średni przypadek: O(log log n) ✅

Dla równomiernie rozłożonych danych:

Najgorszy przypadek: O(n) ❌

Dla nierównomiernie rozłożonych danych:

7. Porównanie: binarne vs interpolacyjne

8. Optymalizacja – unikanie dzielenia przez zero

9. Rekurencyjna implementacja

10. Kiedy używać interpolacji?

✅ Używaj gdy:

  1. Dane równomiernie rozłożone (równe odstępy wartości)
  2. Duże zbiory danych (n > 1000)
  3. Wyszukiwania częste (koszt sortowania już poniesiony)
  4. Znasz rozkład danych

❌ Unikaj gdy:

  1. Dane nierównomierne (duże różnice między sąsiadami)
  2. Małe zbiory (n < 100) – różnica nieznaczna
  3. Dane zawierają duplikaty (może być wolniejsze)

11. Przykłady danych

Dobre dla interpolacji:

Złe dla interpolacji:

12. Benchmark szczegółowy

13. Porównanie algorytmów wyszukiwania

Algorytm Najlepszy Średni Najgorszy Wymaga sortowania Rozkład danych
Liniowe O(1) O(n) O(n) ❌ NIE Dowolny
Binarne O(1) O(log n) O(log n) ✅ TAK Dowolny
Interpolacyjne O(1) O(log log n) O(n) ✅ TAK Równomierny ✅

14. Zastosowania praktyczne

14.1. Książka telefoniczna

14.2. Wyszukiwanie dat

14.3. Dane sensorów (równomierne próbkowanie)

15. Podsumowanie

Wyszukiwanie interpolacyjne:

  • Złożoność czasowa:
  • Najlepszy: O(1)
  • Średni: O(log log n) ← Szybsze niż binarne!
  • Najgorszy: O(n) ← Wolniejsze niż binarne!
  • Złożoność pamięciowa: O(1)
  • WYMAGANE: Lista posortowana + równomierny rozkład

Zalety: - O(log log n) dla równomiernych danych – szybsze niż binarne - Inteligentnie wykorzystuje wartości elementów - Intuicyjne (jak szukanie w książce telefonicznej)

Wady: - O(n) w najgorszym przypadku dla nierównomiernych danych - Bardziej złożone niż binarne - Wymaga równomiernego rozkładu

vs Wyszukiwanie binarne:

Aspekt Interpolacyjne Binarne
Średnia złożoność O(log log n) ✅ O(log n)
Najgorsza O(n) ❌ O(log n) ✅
Rozkład danych Wymagany ❌ Dowolny ✅
Prostota Złożone Prostsze ✅

Kiedy używać: - ✅ Równomierne dane (range, daty, równe odstępy) - ✅ Duże zbiory (n > 1000) - ✅ Znasz rozkład danych

Kiedy NIE używać: - ❌ Nierównomierne dane (użyj binarnego) - ❌ Małe zbiory (różnica nieznaczna) - ❌ Nieznany rozkład (bezpieczniejsze binarne)

Praktyczna rada: W większości przypadków używaj wyszukiwania binarnego (bezpieczniejsze, przewidywalne O(log n)). Interpolacyjne tylko gdy wiesz, że dane są równomierne.

Co dalej warto poznać:

  • Jump search (O(√n))
  • Exponential search
  • Fibonacci search
  • Ternary search (dla funkcji unimodalnych)
Wróć do spisu lekcji