Wyszukiwanie liniowe i binarne: dwie pętle, w których łatwo się pomylić

W poprzedniej części tablica mieszająca odpowiadała na pytanie „czy jest klucz X” w czasie stałym. Teraz cofniemy się o krok i zapytamy, co robić, gdy takiej tablicy nie mamy – bo dane są w zwykłej liście, w pliku, w kolumnie bazy albo po prostu jest ich za mało, żeby budować cokolwiek fantazyjnego.

Wyszukiwanie liniowe i binarne to dwa algorytmy, które każdy zna. Warto je znać dokładniej, bo pierwszy bywa niesłusznie pogardzany, a drugi jest sławny z tego, że prawie nikt nie pisze go poprawnie za pierwszym razem.

Liniowe: niedoceniane

# Python
def find_linear(items, wanted):
    """Przejrzyj po kolei. Nic nie zakłada o danych – i to jest jego siła."""
    for index, value in enumerate(items):
        if value == wanted:
            return index
    return -1

O(n), zero wymagań wstępnych, dwie linijki. Wyszukiwanie liniowe wygrywa częściej, niż sugeruje tabelka złożoności:

• Na krótkich listach. Poniżej kilkudziesięciu elementów narzut na cokolwiek mądrzejszego się nie zwraca, a dane leżą w pamięci obok siebie, więc procesor czyta je błyskawicznie.
• Gdy szukasz raz. Posortowanie n elementów kosztuje O(n log n) – dużo więcej niż jedno przejrzenie listy.
• Gdy warunek jest złożony. „Pierwszy element spełniający trzy warunki naraz” to zawsze przegląd, bo nie da się tego zindeksować.

W Pythonie zresztą rzadko pisze się tę pętlę ręcznie – x in items, items.index(x), next(i for i in items if ...) to wszystko wyszukiwanie liniowe, tylko wykonane w C.

Binarne: szybkie, pod jednym warunkiem

Wyszukiwanie binarne wymaga danych posortowanych i w zamian daje O(log n). Dla miliona elementów to dwadzieścia porównań zamiast miliona.

# Python
def find_binary(items, wanted):
    """Przedział domknięty [lo, hi]; niezmiennik: jeśli wartość istnieje, leży w [lo, hi]."""
    lo, hi = 0, len(items) - 1
    while lo <= hi:                     # <= , bo przedział jest domknięty z obu stron
        mid = (lo + hi) // 2
        if items[mid] == wanted:
            return mid
        if items[mid] < wanted:
            lo = mid + 1                # +1 i -1 gwarantują, że przedział MALEJE
        else:
            hi = mid - 1
    return -1

Cała trudność siedzi w trzech miejscach, w których łatwo o pomyłkę:

1. Warunek pętli. Przy przedziale domkniętym [lo, hi] musi być lo <= hi. Przy półotwartym [lo, hi) – lo < hi, a hi startuje z len(items). Zmieszanie obu konwencji to najczęstszy błąd: pętla albo gubi ostatni element, albo nie kończy się nigdy.
2. Aktualizacja granic. Bez +1 i -1 przedział przestaje się kurczyć i dostajesz pętlę nieskończoną – klasyczny objaw przy dwuelementowej tablicy.
3. Niezmiennik. Zdanie „jeśli szukana wartość istnieje, to leży w [lo, hi]” musi być prawdziwe przed pętlą, po każdym obiegu i po jej zakończeniu. Jeśli potrafisz je zapisać, kod prawie pisze się sam.

Nie pisz tego sam: bisect

Python ma to wszystko gotowe w module bisect, i to w wersji, która odpowiada na pytanie ciekawsze niż „czy jest”:

# Python
from bisect import bisect_left, bisect_right, insort

oceny = [2, 3, 3, 3, 4, 5]

bisect_left(oceny, 3)      # 1 – pierwsza pozycja, na której może stać 3
bisect_right(oceny, 3)     # 4 – pierwsza pozycja ZA wszystkimi trójkami
bisect_right(oceny, 3) - bisect_left(oceny, 3)    # 3 – ile jest trójek, bez zliczania

insort(oceny, 4)           # wstawienie z zachowaniem porządku

bisect_left i bisect_right to w praktyce zapytanie zakresowe: pozwalają policzyć elementy w przedziale albo znaleźć najbliższy większy bez przeglądania listy. Od Pythona 3.10 obie funkcje przyjmują argument key=, więc działają też na listach obiektów bez budowania osobnej listy kluczy.

Uwaga na koszt: insort znajduje miejsce w O(log n), ale samo wstawienie do listy to O(n), bo trzeba przesunąć ogon. Przy wielu wstawieniach lepszą strukturą będzie kopiec albo drzewo – wrócę do tego w dalszych częściach serii.

Ile trzeba zapytań, żeby opłaciło się posortować

To jest pytanie, które warto umieć policzyć na serwetce. Przy k zapytaniach do zbioru n elementów:

• liniowo: k · n
• posortuj raz, potem binarnie: n log₂ n + k · log₂ n

Dla n = 100 000 sortowanie kosztuje około 1,7 mln operacji, a każde zapytanie 17 zamiast 100 000. Próg opłacalności wypada więc przy około 17 zapytaniach – powyżej tego sortowanie zwraca się z nawiązką, poniżej jest stratą.

I to jest dokładnie ten sam rachunek, który wykonuje baza danych, gdy decyduje, czy skorzystać z indeksu, czy przeskanować tabelę. Indeks to nic innego jak trwale utrzymany porządek, dzięki któremu koszt sortowania płacimy raz, przy zapisie, a nie przy każdym zapytaniu. Wrócę do tego w części o B-drzewach.

Dwa warianty, które warto znać

Wyszukiwanie wykładnicze – gdy nie znasz rozmiaru zbioru albo szukana wartość jest prawdopodobnie blisko początku: podwajaj granicę (1, 2, 4, 8…), aż przeskoczysz szukaną wartość, a potem zrób wyszukiwanie binarne w ostatnim przedziale. To technika z galopowania w TimSorcie, które opisywałem w serii o sortowaniu.

Wyszukiwanie interpolacyjne – zamiast celować w środek przedziału, zgaduj pozycję proporcjonalnie do wartości (jak przy szukaniu hasła w słowniku: „Z” otwierasz od końca). Dla danych rozłożonych równomiernie daje O(log log n), ale dla danych skupionych degeneruje się do O(n). Znowu ten sam wzorzec, co przy quicksorcie: świetnie średnio, kiepsko w najgorszym przypadku.

Podsumowanie

Wyszukiwanie binarne wymaga porządku, a utrzymanie porządku w zbiorze, który cały czas się zmienia, to osobny problem: po każdym wstawieniu trzeba by przesuwać pół tablicy. Rozwiązaniem są struktury, które trzymają porządek bez przesuwania czegokolwiek – drzewa poszukiwań. To temat następnej części.