Binäre Suche

Dieses Kapitel behandelt die binäre Suche. Wir stellen uns die Frage, wie die Suche effizienter werden könnte. Das Prinzip der binären Suche ist zuerst den mittleren Eintrag zu wählen und zu prüfen ob sich der gesuchte Wert in der linken oder rechten Hälfte der Liste befindet. Anschließend fährt man rekursiv mit der Hälfte fort, in der sich der Eintrag befindet. Voraussetzung für das binäre Suchverfahren ist, dass die Folge sortiert ist. Das Suchverfahren entspricht dem Entwurfsmuster von Divide-and-Conquer.

Beispiel

Rekursiver Algorithmus

int BinarySearch(int[] F, int k){  
  /*input: Folge F der Länge n, Schlüssel k */
  /*output: Position p */
   return  BinarySearchRec(F, k, 0, F.length-1); //initialer Aufruf
} 
int BinarySearchRec (int[] F, int k, int u, int o) {
  /* input: Folge F der Länge n, Schlüssel k,
        untere Schranke u, obere Schranke o */
  /* output: Position p */ 
 
 m = (u+o)/2;
 if  (F[m] ==  k) return m;
 if  ( u == o) return -1;
 if  (F[m] >  k) return BinarySearchRec(F,k,u,m-1);
 return BinarySearchRec(F,k,m+1,o); 
}

Aufwands Analyse

Das Terminierungs-Theorem besagt, dass der Algorithmus BinarySearch für jede endliche Eingabe F nach endlicher Zeit terminiert. In jedem Rekursionsschritt verkürzt sich die Länge des betrachteten Arrays F um mehr als die Hälfte. Nach endlichen vielen Schritten hat das Array nur noch ein Element und die Suche endet entweder erfolgreich oder erfolglos. Falls das Element vorher gefunden wird terminiert der Algorithmus schon früher.

Das Korrektheits-Theorem besagt, dass falls das Array F ein Element k enthält, gibt BinarySearch(F.k) den Index eines Vorkommens von k zurück. Ansonsten gibt BinarySearch (F,k) den Wert ‐1 zurück. Beweisen kann man das durch die verallgemeinerte Induktion nach der Länge n von F. n=1: Der erste Aufruf von BinarySearchRec ist BinarySearchRec(F,k,0,0) und somit m=0. Ist F[0]=k so wird 0 zurückgegeben, ansonsten ‐1 da 0=0. n>1: Der erste Aufruf von BinarySearchRec ist BinarySearchRec(F,k,0,n‐1) und somit m=(n‐1)/2. Ist F[m]=k, so wird m zurückgegeben. Ansonsten wird rekursiv auf F[0...m‐1] oder F[m+1...n] fortgefahren. Da die Folge sortiert ist, kann k nur in einem der beiden Teile vorhanden sein.

Da die Liste nach jedem Aufruf halbiert wird, haben wir nach dem ersten Teilen der Folge noch n/2 Elemente, nach dem zweiten Schritt n/4 Elemente, nach dem dritten Schritt n/8 Elemente... daher lässt sich allgemein sagen, dass in jedem i-ten Schritt maximal $n/2^{i}$ Elemente, das heißt $log_{2}n$ Vergleiche bei der Suche. Im besten Fall hat die Suche nur einen Vergleich, weil der Suchschlüssel genau in der Mitte liegt. Im schlechtesten Fall und im Durchschnitt für eine erfolgreiche und eine erfolglose Suche liegt die Anzahl der Vergleiche bei $log_{2}n$ .

Rekursionsgleichung

Für die erfolglose Suche ergibt sich folgende Rekursionsgleichung.

$T(n):=\left\{{\begin{array}{ll}\Theta (1)&falls~n=1\\T(n/2)&sonst\end{array}}\right.$

Das Auflösen von T(n) nach Induktion ergibt eine $T(n)=\Theta (log~n)$ Laufzeit für eine erfolglose, also Worst-Case, Suche.

Iterativer Algorithmus

int  BinarySearch(int[] F, int k) {
   /* input: Folge F der Länge n, Schlüssel k */ 
   /*  output: Position p  (0 ≤ p ≤ n-1)  */
 
   int u = 0;
   int o = F.length-1; 
   int m;
   while (u <= o) { 
       m = (u+o)/2;
       if  (F[m] ==  k)
           return m; 
       else
           if (k < F[m]) 
               o = m-1;
           else
               u = m+1; 
 
  }    
  return -1;
}

Der erste Teil des Algorithmus ist die Initialisierung. Die while Schleife, besagt, dass so lange wiederholt werden soll, bis die angegebenen Schranken erreicht sind. Die if Anweisung ist die Abbruchbedingung. Der letzte Teil des Algorithmus (else) passt die obere, bzw. untere Schranke an.

Vergleich der Suchverfahren

Verfahren / #Elemente	$10$	$10^{2}$	$10^{3}$	$10^{4}$
sequenziell (n/2)	$\approx 5$	$\approx 50$	$\approx 500$	$\approx 5000$
binär $log_{2}n$	$\approx 3,3$	$\approx 6,6$	$\approx 9,9$	$\approx 13,3$

Literatur

Da die Vorlesungsinhalte auf dem Buch Algorithmen und Datenstrukturen: Eine Einführung mit Java von Gunter Saake und Kai-Uwe Sattler aufbauen, empfiehlt sich dieses Buch um das hier vorgestellte Wissen zu vertiefen. Die auf dieser Seite behandelten Inhalte sind in Kapitel 5.1.2 zu finden.