Zadanie 2: Wyszukiwanie Binarne

Wstęp

Czy zastanawiałeś się kiedyś, jak komputer znajduje słowo w słowniku w ułamku sekundy? Nie sprawdza każdej strony po kolei! Zamiast tego otwiera go w połowie i sprawdza, czy szukane słowo jest wcześniej, czy później. To jest właśnie wyszukiwanie binarne.

[!IMPORTANT] Wyszukiwanie binarne wymaga, aby dane były posortowane. Bez tego algorytm nie zadziała!

Cel zadania

Napisanie funkcji binarySearch(arr, target), która wykorzystuje metodę "dziel i zwyciężaj" do błyskawicznego odnajdywania elementu w posortowanej tablicy.

Wymagania techniczne

1. Dane: Posortowana tablica liczb.
2. Logika: Wykorzystanie dwóch wskaźników (left, right) do zawężania obszaru poszukiwań.
3. Wydajność: Zrozumienie, dlaczego $O(\log n)$ jest lepsze niż $O(n)$.

Kroki do wykonania

1. Przygotowanie środowiska

Stwórz plik search.js. Przygotujmy w nim dane, na których będziemy operować.

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

[!IMPORTANT] Commit 1: Przygotowanie struktury danych do wyszukiwania binarnego.

2. Implementacja algorytmu

Główna idea polega na sprawdzaniu środkowego elementu i odrzucaniu połowy tablicy w każdym kroku.

function binarySearch(arr, target) {
    let left = 0;
    let right = arr.length - 1;

    while (left <= right) {
        let mid = Math.floor((left + right) / 2);

        if (arr[mid] === target) {
            return mid; // Znaleziono pod indeksem mid
        }

        if (arr[mid] < target) {
            left = mid + 1; // Szukamy w prawej połowie
        } else {
            right = mid - 1; // Szukamy w lewej połowie
        }
    }

    return -1; // Element nie istnieje
}

3. Walidacja działania

Uruchom kod i sprawdź, czy poprawnie znajduje liczby z początku, środka i końca tablicy oraz jak reaguje na brak elementu.

const index = binarySearch(sortedArray, target);
console.log(index !== -1 ? `Znaleziono na pozycji: ${index}` : "Brak elementu");

[!TIP] Wyszukiwanie binarne jest niezwykle szybkie. Nawet dla miliarda elementów potrzebuje maksymalnie około 30 porównań!

[!IMPORTANT] Commit 2: Pełna implementacja i testowanie wyszukiwania binarnego.

Zadanie dla chętnych

Zaimplementuj wyszukiwanie binarne w sposób rekurencyjny. Porównaj czytelność obu rozwiązań.