Sind in der sortierten Liste nur positive, ganzzahlige Schlüssel ohne Duplikate gespeichert, wachsen Schlüsselwerte mindestens so stark wie die Indizes der Elemente.
- i wird höchstens log2 K mal verdoppelt
- Bestimmung des gesuchten Intervalls erfordert maximal
log2 K Schlüsselvergleiche
- Suche innerhalb des Abschnitts (z. B. mit Binärsuche )
erfordert auch höchstens log2 K Schlüsselvergleiche
Gesamtaufwand O ( log2 K )