Zadanie 4: Wyszukiwanie Skokowe (Jump Search)

Wstęp

Wyobraź sobie, że szukasz konkretnego rozdziału w grubej książce. Zamiast wertować kartkę po kartce, zaglądasz co 50 stron. Kiedy zauważysz, że minąłeś szukany rozdział, cofasz się o te 50 stron i wtedy sprawdzasz już każdą kartkę po kolei.

To właśnie jest wyszukiwanie skokowe (Jump Search). Jest to algorytm, który łączy w sobie szybkość skakania po danych z dokładnością wyszukiwania liniowego.

[!IMPORTANT] Podobnie jak wyszukiwanie binarne, Jump Search wymaga posortowanej tablicy.

Cel zadania

Napisanie funkcji jumpSearch(arr, target), która znajdzie indeks szukanego elementu, wykonując skoki o wielkość sqrt(n).

Jak to działa?

Obliczamy krok skoku ($m$): Najbardziej optymalna wartość to pierwiastek kwadratowy z długości tablicy ($\sqrt{n}$).
Skaczemy: Sprawdzamy elementy na indeksach $0, m, 2m, 3m...$ tak długo, aż znajdziemy element większy lub równy target (lub dojdziemy do końca tablicy).
Wyszukiwanie liniowe: Gdy znajdziemy przedział, w którym może być nasza liczba, przeszukujemy go klasycznie (element po elemencie) od ostatniego bezpiecznego punktu.

Wymagania techniczne

Dane: Posortowana tablica liczb.
Krok: Wykorzystanie Math.sqrt() do wyznaczenia optymalnego kroku.
Wydajność: Złożoność czasowa to $O(\sqrt{n})$. Jest wolniejszy niż wyszukiwanie binarne ($O(\log n)$), ale znacznie szybszy niż liniowe ($O(n)$).

Kroki do wykonania

1. Przygotowanie danych

Stwórz plik jump.js. Przygotuj posortowaną tablicę.

const numbers = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91];
const targetValue = 23;

2. Implementacja algorytmu

Zaimplementuj funkcję, która wyznaczy krok i odnajdzie właściwy przedział.

function jumpSearch(arr, target) {
    let n = arr.length;
    let step = Math.floor(Math.sqrt(n));
    let prev = 0;

    // Skakanie do przodu
    while (arr[Math.min(step, n) - 1] < target) {
        prev = step;
        step += Math.floor(Math.sqrt(n));
        if (prev >= n) return -1;
    }

    // Wyszukiwanie liniowe w znalezionym przedziale
    while (arr[prev] < target) {
        prev++;
        // Jeśli doszliśmy do następnego bloku lub końca tablicy
        if (prev === Math.min(step, n)) return -1;
    }

    // Sprawdzenie czy znaleźliśmy element
    if (arr[prev] === target) return prev;

    return -1;
}

3. Testowanie

Sprawdź, jak algorytm poradzi sobie z liczbami na początku, w środku i na końcu tablicy.

Zadania dodatkowe (obowiązkowe)

Wizualizacja skoków: Zmodyfikuj funkcję tak, aby w konsoli wypisywała informację o każdym wykonanym skoku (np. "Skok na indeks 3", "Skok na indeks 6").
Obsługa pustej tablicy: Dodaj zabezpieczenie na początku funkcji – jeśli tablica jest pusta, funkcja powinna od razu zwrócić -1 bez liczenia pierwiastków.
Porównanie wydajności: Stwórz tablicę 10 000 elementów ([1, 2, 3...10000]). Użyj console.time() i console.timeEnd(), aby porównać czas wykonania wyszukiwania skokowego oraz zwykłego wyszukiwania liniowego (Array.indexOf()) przy szukaniu liczby 9999.

Algorytmy: Wyszukiwanie skokowe (Jump Search)