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.

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.