Wyszukiwanie skokowe (Jump Search)

1. Czym jest wyszukiwanie skokowe?

Wyszukiwanie skokowe (jump search, block search) to algorytm wyszukiwania, który łączy liniowe przeskakiwanie bloków z liniowym przeszukiwaniem w bloku.

Idea:

Zamiast sprawdzać każdy element (liniowe) lub dzielić na pół (binarne), przeskakuj bloki o stałym rozmiarze, potem szukaj liniowo w bloku.

Wizualizacja:

Lista: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
Szukamy: 7
Rozmiar skoku: 3

Krok 1: Sprawdź arr[0] = 0
        0 < 7 → skocz dalej

Krok 2: Sprawdź arr[3] = 3
        3 < 7 → skocz dalej

Krok 3: Sprawdź arr[6] = 6
        6 < 7 → skocz dalej

Krok 4: Sprawdź arr[9] = 9
        9 > 7 → cofnij się do bloku [6...9]

Krok 5: Przeszukaj liniowo [6, 7, 8, 9]:
        arr[6]=6 → nie
        arr[7]=7 → ZNALEZIONO!

Łącznie: 5 sprawdzeń (vs 8 dla liniowego)

2. Optymalny rozmiar skoku

Matematycznie udowodniono: Optymalny rozmiar skoku = √n

Dlaczego √n?

Liczba skoków: n/√n = √n
Wyszukiwanie liniowe w bloku: √n (najgorszy przypadek)

Łącznie: √n + √n = 2√n ≈ O(√n)

3. Implementacja podstawowa

4. Wizualizacja z debugiem

Wynik:

Szukam: 7
Lista: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
Rozmiar skoku: √10 = 3

=== FAZA 1: Przeskakiwanie bloków ===
Krok 1: Sprawdzam arr[2] = 2
  2 < 7 → skocz dalej
  Blok: arr[0:3]

Krok 2: Sprawdzam arr[5] = 5
  5 < 7 → skocz dalej
  Blok: arr[3:6]

Krok 3: Sprawdzam arr[8] = 8
  8 > 7 → znaleziono blok

Znaleziono blok: arr[6:9]

=== FAZA 2: Wyszukiwanie liniowe w bloku ===
Sprawdzam arr[6] = 6
  6 < 7 → idź dalej
Sprawdzam arr[7] = 7
✅ ZNALEZIONO: arr[7] = 7

Łącznie sprawdzeń: 3 (skoki) + 2 (liniowe) = 5

5. Złożoność czasowa: O(√n)

Analiza:

Faza 1 (skoki):        n/√n = √n kroków (najgorszy)
Faza 2 (liniowe):      √n kroków (najgorszy)

Łącznie: √n + √n = 2√n = O(√n)

Porównanie:

n Liniowe O(n) Binarne O(log n) Jump O(√n)
100 100 7 20
1,000 1,000 10 63
10,000 10,000 14 200
100,000 100,000 17 632

Wniosek: Jump search jest wolniejszy od binarnego, ale szybszy od liniowego.

6. Złożoność pamięciowa: O(1)

Jump search NIE wymaga dodatkowej pamięci (jak binarne).

7. Warianty rozmiaru skoku

7.1. Stały rozmiar

Użycie: Gdy znasz charakterystykę danych.

7.2. Adaptacyjny rozmiar

8. Porównanie: Jump vs Binary vs Linear

Wniosek: Binary zawsze najszybsze, Jump średnio, Linear najwolniejsze.

✅ Używaj gdy:

  1. Skok wstecz jest kosztowny
  2. Binarne wymaga "cofania się" (skoki wstecz)

  3. Jump tylko skoki do przodu + liniowe

  4. Dane na taśmie/linked list

  5. Binarne wymaga dostępu losowego

  6. Jump działa sekwencyjnie

  7. Znasz orientacyjnie, gdzie szukać

  8. Możesz dostosować rozmiar skoku

❌ Unikaj gdy:

  1. Dostęp losowy tani (tablice) → użyj binarnego
  2. Małe dane (n < 100) → różnica nieznaczna
  3. Potrzebujesz O(log n) → binarne lepsze

10. Jump Search dla linked list

Główna zaleta jump search – działa dla linked list:

Zaleta: Binarne nie działa dla linked list (brak dostępu losowego)!

11. Exponential Search (pokrewny algorytm)

Exponential search łączy jump search z binarnym:

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

12. Porównanie algorytmów wyszukiwania

Algorytm Złożoność Pamięć Wymaga sortowania Dostęp losowy Skoki wstecz
Liniowe O(n) O(1) ❌ NIE ❌ NIE ❌ NIE
Binarne O(log n) O(1) ✅ TAK ✅ TAK ✅ TAK
Jump O(√n) O(1) ✅ TAK ❌ NIE ❌ NIE
Interpolacyjne O(log log n) O(1) ✅ TAK ✅ TAK ✅ TAK
Exponential O(log n) O(1) ✅ TAK ✅ TAK ✅ TAK

13. Benchmark szczegółowy

14. Podsumowanie

Wyszukiwanie skokowe:

  • Złożoność czasowa: O(√n)
  • Złożoność pamięciowa: O(1)
  • WYMAGANE: Lista posortowana
  • Optymalny skok: √n

Zalety: - Lepsze niż liniowe O(√n) vs O(n) - Tylko skoki do przodu (bez cofania) - Działa dla linked list (nie wymaga dostępu losowego) - O(1) pamięci

Wady: - Wolniejsze niż binarne O(√n) vs O(log n) - Wymaga sortowania - Rzadko używane w praktyce (binarne lepsze)

Porównanie:

n = 10,000:
- Liniowe:        ~10,000 operacji
- Jump:           ~200 operacji (50x szybsze!)
- Binarne:        ~14 operacji (714x szybsze!)

Kiedy używać: - ✅ Linked lists (nie ma dostępu losowego) - ✅ Skoki wstecz kosztowne (taśmy, strumienie) - ✅ Dane sekwencyjne (pliki sekwencyjne)

Kiedy NIE używać: - ❌ Tablice z dostępem losowym → użyj binarnego - ❌ Potrzebujesz O(log n) → binarne/exponential - ❌ Małe dane → różnica nieznaczna

Praktyczna rada: W większości przypadków używaj wyszukiwania binarnego (O(log n), uniwersalne). Jump search tylko dla struktur sekwencyjnych (linked list, taśmy).

Pokrewne algorytmy: - Exponential search: O(log n) – lepsze niż jump - Fibonacci search: O(log n) – używa liczb Fibonacciego - Interpolation search: O(log log n) – dla równomiernych danych

Co dalej warto poznać:

  • Exponential search (jump wykładniczy + binarne)
  • Fibonacci search
  • Ternary search (dla funkcji unimodalnych)
  • Haszowanie (O(1) średnio)
Wróć do spisu lekcji