Jak działa algorytm wyszukiwania binarnego?

Wyszukiwanie binarne działa, analizując posortowaną tablicę, dzieląc kolejno zakres wyszukiwania na pół.

1. Inicjalizacja: Określa się lewą i prawą granicę zakresu wyszukiwania (zazwyczaj początek i koniec tablicy).
2. Porównanie: Oblicza się indeks środka zakresu. Wartość na tym indeksie jest porównywana z poszukiwanym elementem.
3. Zmniejszenie zakresu:
   • Jeśli wartość w środku jest równa poszukiwanemu, element został znaleziony.
   • Jeśli wartość w środku jest większa od poszukiwanego, wyszukiwanie kontynuuje się w lewej połowie zakresu. Prawa granica przesuwa się na środek - 1.
   • Jeśli wartość w środku jest mniejsza od poszukiwanego, wyszukiwanie kontynuuje się w prawej połowie zakresu. Lewa granica przesuwa się na środek + 1.
4. Powtarzanie: Kroki 2 i 3 powtarzają się, aż element zostanie znaleziony lub zakres wyszukiwania stanie się pusty.

Złożoność algorytmu to O(log n), co jest znacznie bardziej wydajne niż wyszukiwanie liniowe dla dużych tablic.

Przykład implementacji w Pythonie:

def binary_search(arr, target):
    """
    Implementacja wyszukiwania binarnego.
    Przyjmuje posortowaną tablicę i poszukiwany wartość.
    Zwraca indeks elementu lub -1, jeśli element nie zostanie znaleziony.
    """
    left, right = 0, len(arr) - 1

    while left <= right:
        mid = (left + right) // 2  # Obliczanie indeksu środka
        mid_val = arr[mid]      # Pobranie wartości w środku

        if mid_val == target:
            return mid  # Element znaleziony
        elif mid_val < target:
            left = mid + 1  # Szukany jest większy, szukaj w prawej części
        else: # mid_val > target
            right = mid - 1 # Szukany jest mniejszy, szukaj w lewej części

    return -1 # Element nie znaleziony