Zadanie 6: Wyszukiwanie Fibonacciego (Fibonacci Search)

Wstęp

Czy wiesz, że natura i matematyka mogą pomóc w przeszukiwaniu danych? Ciąg Fibonacciego ($0, 1, 1, 2, 3, 5, 8...$) znajduje zastosowanie nie tylko w przyrodzie, ale również w informatyce.

Wyszukiwanie Fibonacciego to algorytm typu "dziel i zwyciężaj", który podobnie jak wyszukiwanie binarne, przeszukuje posortowaną tablicę. Jego unikalną cechą jest to, że nie używa operatora dzielenia (/) – wystarczy mu dodawanie i odejmowanie. Historycznie było to kluczowe dla procesorów, które wykonywały dzielenie znacznie wolniej.

[!IMPORTANT] Algorytm wymaga posortowanej tablicy.

Cel zadania

Napisanie funkcji fibonacciSearch(arr, target), która wykorzystuje kolejne liczby Fibonacciego do zawężania obszaru poszukiwań.

Jak to działa?

Znalezienie liczb Fibonacciego: Znajdujemy najmniejszą liczbę Fibonacciego $F_k$, która jest większa lub równa długości tablicy $n$.
Dzielenie przedziału: Używamy dwóch poprzednich liczb z ciągu ($F_{k-1}$ oraz $F_{k-2}$) do wyznaczenia indeksu podziału.
Eliminacja części:
- Jeśli szukany element jest większy, przesuwamy zakres i zmieniamy liczby Fibonacciego na mniejsze.
- Jeśli jest mniejszy, zostajemy w obecnym zakresie i również zmieniamy liczby na mniejsze.

Wymagania techniczne

Dane: Posortowana tablica liczb.
Logika: Wygenerowanie ciągu Fibonacciego wewnątrz funkcji lub przed nią.
Wydajność: Złożoność czasowa to $O(\log n)$, podobnie jak w wyszukiwaniu binarnym.

Kroki do wykonania

1. Inicjalizacja liczb Fibonacciego

Zacznij od przygotowania trzech zmiennych przechowujących kolejne liczby ciągu ($F_k, F_{k-1}, F_{k-2}$).

let fibM2 = 0; // (k-2)
let fibM1 = 1; // (k-1)
let fibM = fibM2 + fibM1; // k

// Znajdź najmniejszą liczbę Fibonacciego >= n
while (fibM < n) {
    fibM2 = fibM1;
    fibM1 = fibM;
    fibM = fibM2 + fibM1;
}

2. Implementacja pętli wyszukiwania

Będziemy przesuwać "offset" tablicy i sprawdzać elementy.

function fibonacciSearch(arr, target) {
    let n = arr.length;
    let offset = -1;

    // (Kod inicjalizacji ciągu Fibonacciego tutaj...)

    while (fibM > 1) {
        let i = Math.min(offset + fibM2, n - 1);

        if (arr[i] < target) {
            // Przesuwamy się w prawo
            fibM = fibM1;
            fibM1 = fibM2;
            fibM2 = fibM - fibM1;
            offset = i;
        } else if (arr[i] > target) {
            // Zostajemy w lewo
            fibM = fibM2;
            fibM1 = fibM1 - fibM2;
            fibM2 = fibM - fibM1;
        } else {
            return i; // Znaleziono!
        }
    }

    // Sprawdzenie ostatniego elementu
    if (fibM1 && arr[offset + 1] === target) return offset + 1;

    return -1;
}

3. Testowanie

Przetestuj funkcję dla tablicy 15-elementowej. Sprawdź, co się stanie, gdy szukany element znajduje się na ostatniej pozycji.

Zadania dodatkowe (obowiązkowe)

Analiza kroków: Dodaj licznik operacji. Sprawdź, ile razy wykonała się pętla while dla tablicy o rozmiarze 100, gdy szukasz elementu, którego nie ma w środku.
Zabezpieczenie przed ujemnymi: Upewnij się, że algorytm zachowa się poprawnie, jeśli otrzyma tablicę o długości 0.
Własny ciąg: Zmodyfikuj algorytm tak, aby liczby Fibonacciego były generowane dynamicznie tylko raz na początku i przechowywane w małej tablicy fibs, z której będziesz korzystać podczas wyszukiwania.

Algorytmy: Wyszukiwanie Fibonacciego (Fibonacci Search)