Algorytmy wyszukiwania O(log n) vs O(n) w Pythonie

Porównanie algorytmów wyszukiwania: od O(n) do O(log n) dla programistów

W tablicy zawierającej milion elementów liniowe wyszukiwanie wymaga nawet 10 milionów operacji, podczas gdy wyszukiwanie binarne ogranicza się do zaledwie 24 porównań. Przegląd czterech algorytmów wyszukiwania w Pythonie — z analizą złożoności obliczeniowej i praktycznymi wskazówkami do wyboru. W tym także ochrona przed przepełnieniem, funkcje lower_bound/upper_bound oraz przykłady zadań z LeetCode.

Zadanie wyszukiwania: w kolekcji arr znaleźć indeks wartości target lub zwrócić -1. Kolekcja może być posortowana lub nie, statyczna lub dynamiczna. Zastosowania: wyszukiwanie kodów SKU w e-commerce (miliony artykułów), weryfikacja ID transakcji w fintech.

Wyszukiwanie liniowe dla danych nieposortowanych

Działa na dowolnych kolekcjach. Sprawdza kolejne elementy sekwencyjnie.

Implementacja:

def linear_search(arr, target):
    for i, val in enumerate(arr):
        if val == target:
            return i
    return -1

Złożoność:

• Czas: O(n) w przypadku średnim i pesymistycznym, O(1) w optymistycznym.
• Pamięć: O(1).

Wyszukiwanie binarne i jego warianty

Wymaga posortowanej tablicy. Dzieli zakres na pół w każdej iteracji.

Implementacja iteracyjna: używaj mid = left + (right - left) // 2, aby uniknąć przepełnienia (ważne w C++/Java; w Pythonie bezpieczne domyślnie).

def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        if arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

def lower_bound(arr, target):
    left, right = 0, len(arr)
    while left < right:
        mid = (left + right) // 2
        if arr[mid] < target:
            left = mid + 1
        else:
            right = mid
    return left

def upper_bound(arr, target):
    left, right = 0, len(arr)
    while left < right:
        mid = (left + right) // 2
        if arr[mid] <= target:
            left = mid + 1
        else:
            right = mid
    return left

# Przykład
sorted_arr = [1, 3, 3, 5, 7, 9]
print(binary_search(sorted_arr, 5))  # 3
print(lower_bound(sorted_arr, 3))     # 1
print(upper_bound(sorted_arr, 3))     # 3

Złożoność: O(log n) czas, O(1) pamięć.

lower_bound zwraca pozycję wstawienia po lewej stronie target, upper_bound — po prawej. Przydatne przy duplikatach i zadaniach z LeetCode.

Wyszukiwanie eksponencjalne dla danych strumieniowych

Dla posortowanych tablic o nieznanej długości lub gdy target znajduje się blisko początku. Najpierw określa zakres metodą eksponencjalnego rozszerzania granic, a następnie stosuje wyszukiwanie binarne.

def exponential_search(arr, target):
    if not arr:
        return -1
    if arr[0] == target:
        return 0

    bound = 1
    while bound < len(arr) and arr[bound] < target:
        bound *= 2

    left = bound // 2
    right = min(bound, len(arr) - 1)
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        if arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

# Przykład
big_arr = list(range(1_000_000))
print(exponential_search(big_arr, 123456))  # 123456

Złożoność: O(log i), gdzie i to pozycja elementu; pesymistycznie O(log n), pamięć O(1).

Wyszukiwanie haszujące dla kolekcji dynamicznych

Średnia złożoność O(1) dzięki tablicom haszującym (set/dict w Pythonie).

def hash_search_set(arr, target):
    s = set(arr)
    return target in s

def hash_search_dict(pairs, key):
    d = dict(pairs)
    return d.get(key)

# Przykład
nums = [10, 20, 30, 40]
print(hash_search_set(nums, 30))  # True
pairs = [("a", 1), ("b", 2)]
print(hash_search_dict(pairs, "b"))  # 2

Złożoność: O(1) średnio, O(n) pesymistycznie (kolizje), pamięć O(n).

Wskazówki dotyczące wyboru algorytmu

• Nieposortowana tablica: wyszukiwanie liniowe dla N < 100 lub rzadkich zapytań.
• Posortowana, statyczna kolekcja: wyszukiwanie binarne.
• Dynamiczna z częstymi wstawieniami: tablica haszująca (gdy kolejność nie ma znaczenia).
• Dane strumieniowe / nieznany rozmiar: wyszukiwanie eksponencjalne.

| Algorytm | Średni czas | Pesymistyczny czas | Pamięć | Wymagania |

|----------|-------------|--------------------|--------|-----------|

| Liniowy | O(n) | O(n) | O(1) | Dowolna |

| Binarne | O(log n) | O(log n) | O(1) | Posortowana |

| Eksponencjalne | O(log i) | O(log n) | O(1) | Posortowana |

| Haszujące | O(1) | O(n) | O(n) | Klucze haszowalne |

Kluczowe wnioski

• Dla 10 mln elementów wyszukiwanie binarne wymaga zaledwie 24 operacji — w porównaniu do 10 mln przy liniowym.
• Zawsze stosuj bezpieczną formułę mid w wyszukiwaniu binarnym.
• Tablice haszujące zużywają O(n) pamięci, ale zapewniają średni czas O(1).
• Funkcje lower_bound i upper_bound są niezbędne przy pracy z duplikatami i określaniem pozycji wstawienia.
• Wyszukiwanie eksponencjalne jest optymalne, gdy szukany element znajduje się bliżej początku dużej tablicy.

— Editorial Team