Jaki algorytm ma złożoność logarytmiczną O(log n)?

Algorytm wyszukiwania binarnego (lub dychotomicznego) ma złożoność czasową logarytmiczną O(log n).

Zasada działania wyszukiwania binarnego:

1. Wymaga posortowanej tablicy (lub listy).
2. Na każdym kroku porównuje poszukiwany element z elementem w środku aktualnego zakresu wyszukiwania.
3. Jeśli elementy się zgadzają, wyszukiwanie kończy się.
4. Jeśli poszukiwany element jest mniejszy od środka, wyszukiwanie kontynuuje się w lewej połowie zakresu.
5. Jeśli poszukiwany element jest większy od środka, wyszukiwanie kontynuuje się w prawej połowie zakresu.
6. Zakres wyszukiwania jest za każdym razem zmniejszany do połowy.

Przykład implementacji w Pythonie:

# Funkcja wyszukiwania binarnego
def binary_search(arr, target):
    low = 0
    high = len(arr) - 1

    while low <= high:
        mid = (low + high) // 2
        mid_val = arr[mid]

        if mid_val == target:
            return mid  # Element znaleziony, zwraca indeks
        elif mid_val < target:
            low = mid + 1  # Ignoruje lewą połowę
        else:
            high = mid - 1  # Ignoruje prawą połowę

    return -1  # Element nie znaleziony

# Przykład użycia
# posortowana_lista = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
# cel = 23
# wynik = binary_search(posortowana_lista, cel)
# if wynik != -1:
#     print(f"Znaleziono element na indeksie: {wynik}")
# else:
#     print("Nie znaleziono elementu")

Złożoność logarytmiczna wynika z faktu, że liczba operacji jest proporcjonalna do logarytmu rozmiaru danych wejściowych (n), ponieważ na każdym kroku przestrzeń wyszukiwania jest zmniejszana do połowy.