Analyse der Laufzeit der binären Suche

Beh.:

In einem Schleifendurchlauf schrumpft ein Intervall der Länge 2^k - 1 auf ein Intervall der Länge 2^{k - 1} - 1 .

Beweis:

Sei Länge vom alten Intervall =

2^k - 1 =

2^k =

2^{k - 1} =

2^{k - 1} - 1 = =

= neue Intervalllänge im THEN-Zweig

Korollar:

2^k - 1 Zahlen verursachen höchstens k Schleifendurchläufe, da nach k Halbierungen die Intervallänge 1 beträgt.

Beispiel für eine Folge von 31 sortierten Zahlen:

Schleifendurchlauf 1 2 3 4 5

aktuelle Intervalllänge 2⁵ - 1 2⁴ - 1 2³ - 1 2² - 1 2¹ - 1

= 31 = 15 = 7 = 3 = 1

Anders formuliert:
n Zahlen verursachen höchstens n Schleifendurchläufe.