Sinnvoll, wenn der Schlüsselwert im betreffenden Bereich einigermaßen gleichverteilt ist

erfordert dann im Mittel lediglich

log2 log2n + 1

Schlüsselvergleiche

Im schlechtesten Fall

(stark ungleichmäßige Werteverteilung) entsteht jedoch

linearer Suchaufwand ( O ( n ) )