Algorytm charakteryzuje o wiele lepsza średnia złożoność obliczeniowa niż zwykłego wyszukiwania binarnego, wynosi bowiem a nie Ta złożoność jest osiągana tylko dla danych mających rozkład jednostajny, w przypadku pesymistycznym jest jednak liniowa. Jak podaje Knuth, testy empiryczne wykazują, że podejście to dobrze sprawdza się dla bardzo dużych rozmiarów tablic, dla niewielkich nie widać wyraźnej przewagi ze względu na bardziej złożone wyliczanie indeksu
Pomysłodawcą metody był W.W. Peterson, została użyta do wyszukiwania w posortowanych plikach; została ona opracowana ok. 1957 roku.
Zobacz też binarne drzewo poszukiwań metoda równego podziału tablica mieszająca wyszukiwanie liniowe
Bibliografia Donald Knuth, Sztuka programowania, T. III, Sortowanie i wyszukiwanie, WNT 2002
Kategoria:Algorytmy wyszukiwania