Zadanie 5: Wyszukiwanie Wykładnicze (Exponential Search)

Wstęp

Wyobraź sobie, że lecisz samolotem nad autostradą i szukasz konkretnego samochodu. Najpierw sprawdzasz kilometr 1, potem 2, potem 4, 8, 16... podwajasz dystans tak długo, aż miniesz cel. Kiedy wiesz, że samochód jest między 16 a 32 kilometrem, lądujesz i wtedy przeszukujesz ten konkretny fragment.

To właśnie jest wyszukiwanie wykładnicze (Exponential Search). Jest niezwykle skuteczne, gdy szukany element znajduje się blisko początku tablicy lub gdy jej rozmiar jest nieznany (teoretycznie nieskończony).

[!IMPORTANT] Algorytm ten wymaga posortowanej tablicy i opiera się na wydajności wyszukiwania binarnego.

Cel zadania

Napisanie funkcji exponentialSearch(arr, target), która najpierw znajdzie zakres, a następnie przeszuka go metodą binarną.

Jak to działa?

Sprawdzenie początku: Jeśli element jest pod indeksem 0, zwracamy go od razu.
Szukanie zakresu: Zaczynamy od indeksu 1 i podwajamy go ($1, 2, 4, 8...$) dopóki arr[i] jest mniejsze od target i nie przekroczyliśmy końca tablicy.
Wyszukiwanie binarne: Gdy znajdziemy zakres (od i/2 do min(i, n-1)), wykonujemy w nim klasyczne wyszukiwanie binarne.

Wymagania techniczne

Dane: Posortowana tablica liczb.
Zależność: Musisz posiadać (lub napisać) funkcję wyszukiwania binarnego.
Wydajność: Złożoność czasowa to $O(\log i)$, gdzie $i$ to pozycja elementu. Dla dużych tablic, jeśli szukamy czegoś na początku, jest to szybsze niż zwykłe wyszukiwanie binarne ($O(\log n)$).

Kroki do wykonania

1. Przygotowanie narzędzi

Przygotuj funkcję pomocniczą wyszukiwania binarnego, która obsługuje zakresy low i high.

function binarySearch(arr, target, low, high) {
    while (low <= high) {
        let mid = Math.floor((low + high) / 2);
        if (arr[mid] === target) return mid;
        if (arr[mid] < target) low = mid + 1;
        else high = mid - 1;
    }
    return -1;
}

2. Implementacja wyszukiwania wykładniczego

Stwórz funkcję główną, która podwaja indeksy.

function exponentialSearch(arr, target) {
    if (arr.length === 0) return -1;
    if (arr[0] === target) return 0;

    let i = 1;
    while (i < arr.length && arr[i] <= target) {
        i = i * 2;
    }

    // Wywołujemy binSearch w znalezionym przedziale
    return binarySearch(arr, target, i / 2, Math.min(i, arr.length - 1));
}

3. Testowanie

Przetestuj algorytm na tablicy o rozmiarze 20, szukając elementów o niskich i wysokich indeksach.

Zadania dodatkowe (obowiązkowe)

Wypisanie potęg: Dodaj do pętli while instrukcję console.log, która pokaże, jakie indeksy (potęgi liczby 2) są sprawdzane przed przejściem do wyszukiwania binarnego.
Obsługa błędu: Co się stanie, jeśli tablica będzie miała tylko jeden element? Upewnij się, że Twój kod nie wygeneruje błędu "out of bounds".
Analiza porównawcza: Wyszukiwanie binarne w tablicy o rozmiarze 1 000 000 elementów o stałej wartości (np. same jedynki) szuka zawsze w $log_2(1000000) \approx 20$ krokach. Policz, ile kroków wykona wyszukiwanie wykładnicze, jeśli szukany element znajduje się na 10. pozycji.

Algorytmy: Wyszukiwanie wykładnicze (Exponential Search)