prev up next

Previous: Analyse der Laufzeit der linearen Suche Up: Lineare und binäre Suche Next: Klassenmethoden

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.


prev up next
Previous: Analyse der Laufzeit der linearen Suche Up: Lineare und binäre Suche Next: Klassenmethoden