Wyszukiwanie blokowe

Metoda wyszukiwania blokowego polega na podzieleniu danych wejściowych na pewną ilość równolicznych podzbiorów (ostatni może zawierać mniej elementów). Aby algorytm był optymalny ilość bloków powinna być przybliżeniem pierwiastka kwadratowego z ilości elementów. Następnie porównujemy szukany klucz z ogranicznikami przedziałów i po znalezieniu odpowiedniego podzbioru przeszukujemy go liniowo.

Statystyka:

Wyszukiwanie blokowe wymaga średnio sqrt(n) porównań.