- Element an der Position i = F k-2 wird mit dem Schlüssel K verglichen
- Wird Gleichheit festgestellt, endet die Suche erfolgreich.
- Ist K größer, wird der rechte Bereich mit F k-1 -1
Elementen, ansonsten der linke Bereich mit F k-2 -1
Elementen auf dieselbe Weise durchsucht.
- für n = F k -1 sind im schlechtesten Fall k-2 Suchschritte
notwendig, d. h. O ( k ) Schlüsselvergleiche
- Da gilt F k ? c + 1.618 k , folgt
C max ( n ) = O ( log 1.618 ( n+1 ) ) = O ( log2 n) .