Wyszukiwanie binarne: Różnice pomiędzy wersjami

Algorytm charakteryzuje o wiele lepsza średnia [[Asymptotyczne tempo wzrostu|złożoność obliczeniowa]] niż zwykłego wyszukiwania binarnego, wynosi bowiem <math>O\Theta(\log \log n)</math>, a nie <math>O(\log n)</math>. Złożoność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 <math>c</math>.

Pomysłodawcą metody był W.W. Peterson, została użyta do wyszukiwania w posortowanych plikach; została ona opracowana ok. 1957 roku.