Zadanie 3: Wyszukiwanie Interpolacyjne

Wstęp

Wyszukiwanie binarne zawsze zagląda w sam środek przedziału. Ale czy to zawsze jest najmądrzejsze? Wyobraź sobie, że szukasz nazwiska "Zieliński" w książce telefonicznej. Czy otwierasz ją na literze "M" (w połowie), czy raczej bliżej końca?

Wyszukiwanie interpolacyjne działa podobnie – szacuje pozycję elementu na podstawie jego wartości. Jeśli szukana liczba jest bliska wartości minimalnej w przedziale, algorytm sprawdzi początkowe indeksy. Jeśli jest bliska maksymalnej – końcowe.

[!IMPORTANT] Podobnie jak wyszukiwanie binarne, algorytm ten wymaga posortowanej tablicy. Najlepiej sprawdza się, gdy dane są rozłożone równomiernie (np. [10, 20, 30, 40...]).

Cel zadania

Napisanie funkcji interpolationSearch(arr, target), która wykorzystuje wzór na proporcję do szybkiego odnajdywania elementu.

Wymagania techniczne

1. Dane: Posortowana tablica z równomiernie rozłożonymi liczbami.
2. Logika: Wykorzystanie wzoru na pozycję (pos): $$pos = low + \left\lfloor \frac{(target - arr[low]) \cdot (high - low)}{arr[high] - arr[low]} \right\rfloor$$
3. Wydajność: Średnia złożoność to $O(\log(\log n))$, co czyni go niezwykle szybkim dla dużych zbiorów danych.

Kroki do wykonania

1. Przygotowanie danych

Stwórz plik interpolation.js. Przygotuj tablicę, która ma regularne odstępy między liczbami.

const numbers = [10, 20, 30, 40, 50, 60, 70, 80, 90, 100];
const targetValue = 70;

2. Implementacja algorytmu

Zaimplementuj pętlę, która będzie zawężać zakres poszukiwań tak długo, jak target mieści się w granicach arr[low] i arr[high].

function interpolationSearch(arr, target) {
    let low = 0;
    let high = arr.length - 1;

    while (low <= high && target >= arr[low] && target <= arr[high]) {
        // Jeśli w przedziale jest tylko jeden element, sprawdzamy go
        if (low === high) {
            return arr[low] === target ? low : -1;
        }

        // Obliczamy szacowaną pozycję na podstawie proporcji
        let pos = low + Math.floor(
            ((target - arr[low]) * (high - low)) / (arr[high] - arr[low])
        );

        // Znaleziono element!
        if (arr[pos] === target) {
            return pos;
        }

        // Jeśli target jest większy, szukamy w prawej części
        if (arr[pos] < target) {
            low = pos + 1;
        } 
        // Jeśli target jest mniejszy, szukamy w lewej części
        else {
            high = pos - 1;
        }
    }

    return -1; // Element nie został znaleziony
}

3. Testowanie

Sprawdź działanie algorytmu dla wartości obecnych w tablicy oraz tych, których w niej nie ma.

const result = interpolationSearch(numbers, targetValue);
console.log(result !== -1 ? `Element znaleziony pod indeksem: ${result}` : "Nie znaleziono elementu.");

[!TIP] Jeśli dane są rozłożone bardzo nierównomiernie (np. [1, 2, 3, 1000, 1001]), wyszukiwanie interpolacyjne może działać gorzej niż binarne (nawet $O(n)$).

Zadanie dla chętnych

Dodaj do swojej funkcji licznik porównań. Porównaj, ile kroków potrzebuje wyszukiwanie interpolacyjne, a ile binarne dla tablicy 100 kolejnych liczb (1-100) przy szukaniu liczby 95.