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$	$=$	$\mbox{ rechts } - \mbox{ links } +1$
$\Rightarrow$	$2^{k}$	$=$	$\mbox{ rechts } - \mbox{ links } +2$
$\Rightarrow$	$2^{k-1}$	$=$	$\frac{\mbox{ rechts }- \mbox{ links}} {2} +1$
$\Rightarrow$	$2 ^{k - 1} -1$	$=$	$\frac{\mbox{ rechts } - \mbox{ links}} {2}= \frac{\mbox{ rechts } +\mbox{ rechts } - \mbox{ links } - \mbox{ rechts}}{2}$
		$=$	$\mbox{ rechts }-(\frac{\mbox{ links } + \mbox{ rechts }} {2} +~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^{5}-1$	$2^{4}-1$	$2^{3}-1$	$2^{2}-1$	$2^{1}-1$
	$=31$	$=15$	$=7$	$=3$	$=1$

Anders formuliert:
$n$ Zahlen verursachen höchstens $\log_{2}n$ Schleifendurchläufe.