Die Binäre Suche

Was ist die binäre Suche eigentlich und was setzt Sie voraus? 

Die binäre Suche ist ein "sortierter" Suchalgorithmus, welcher eine sortierte Menge voraussetzt damit er einwandfrei funktioniert.

Nehmen wir einmal an, dass wir n sortierte Datenwerte haben, z.B. 1000 Bücher, die alphabetisch sortiert sind. Das heisst wir haben (unter der Bedingung, dass wir unter jedem Buchstaben eine Reihe haben) 26 verschiedene Reihen(A-Z).

Nun wollen wir das Buch Marquis de Sade , das lasterhafte Leben der Juliette finden und können sequentielle vorgehen, dass heisst von Anfang an jedes Buch überprüfen und hätten schlimmenstenfalls 1000-(26 falls alle Reihen 1 sind und nur die Reihe(M) vorkommt) Schritte bis zum Ergebnis und bei der sequentiellen Suche im Mittel n/2 Suchschritte.

Bei der Binären Suche gehen wir jedoch auf andere Weise vor. Hier rufen wir einfach den Schlüssel("Bücherregal","Marquis des Sade, das lasterhafte Leben der Juliette",1,1000) auf. In diesem Fall schauen wir dann erstmal genau in die Mitte bzw. der linke Wert wird auf 501 gesetzt und danach der Rechte Wert auf 751 usw.

Die Formel dazu ist Recht einfach: Solange der linke Wert kleiner oder gleich dem rechten Wert ist, ist die Mitte (links+rechts)/2 

Wenn der sich daraus ergebende Wert dem Schlüssel (Marquis de Sade, das lasterhafte Leben der Juliette) entspricht, wird das Ergebnis zurückgegeben.

Wenn die Mitte größer als der gesuchte Schlüssel ist dann ist der rechte Werte = Mitte-1

Und wenn die Mitte kleiner als der Schlüssel ist dann wird der linke Wert = Mitte +1

Wir können den Suchalgorithmus nun relativ simpel auf iterativem Weg in Java implementieren und ich verwende hierzu ein Array mit 1000 int Werten, welche per Zufall ausgewählt und sortiert werden. Das entspricht dann noch nicht der fertigen Such-Klasse, sondern stellt zuerst einmal nur ein Beispiel dar.

import java.util.*;
public class binaereSuche2 {

   
    public static void bSuche(int[]werte,int suchwert){
        int links=werte.length-werte.length;
        int rechts=werte.length-1;
        int zaehler=1;
       
        while(links<=rechts){
            int mitte=(links+rechts)/2;
           
         if(suchwert==werte[mitte]){
             System.out.print("Suchvorgänge: "+zaehler);
             System.out.println("   "+"Wert= "+werte[mitte]+" ");
           
             break;
         }
         else if(suchwert<werte[mitte]){
             rechts=mitte-1;
             
         }
         else if(suchwert>werte[mitte]){
             links=mitte+1;
             
         }
         zaehler++;
        }
    }
       
        public static void main (String[] args){
           
            int [] suchArray=new int[10000000];
           
            for(int i=0;i<suchArray.length;i++){
                suchArray[i]=i;
            }
            bSuche(suchArray,2500000);
       
}

Wie wir hier sehen legen wir ein Array mit 100 Millionen Werten an um dann die Zahl 2 Millionen und 500 Tausen zu suchen. Praktischerweise teilt und uns die implementierte Methode gleich die korrekte Anzahl an Suchschritten mit, bevor Sie beendet wird.

wir sehen, dass wir bei einer solchen Menge an Werten niemals mehr als 27 Durchläufe der Schleife haben, somit ist die Methode sehr effektiv.

Woran liegt das? Ein kleiner mathematischer Exkurs:

Wie oft lässt sich ein Liste maximal halbieren, bzw. wie viele Einträge wir mit einer bestimmten Anzahl von Vergleichen durchsuchen können?

Mit 1em Vergleich können wir 2 Einträge durchsuchen (boolesche Logik), mit 2 dann 4 Einträge und mit 3 schon 8 Einträge. Mit n Vergleichen können wir also 2*2*2*...*n = 2ⁿ Einträge durchsuchen.

Somit gilt, nach den Regeln der Exponentialrechnung wenn a=b^x dann ist x=log_b a:

Dadurch gilt im Falle des binären, also 2er Logarithmus bei 100000000 Werten suchen wir log₂ 100000000 = 26.575 Mal. Da es keine halben Vergleiche bei der binären Suche gibt ergeben sich daraus maximal 27 Schritte um den gesuchten Wert zu finde, falls dieser vorhanden ist.

Mann könnte den Algorithmus natürlich auch verbessern indem man Fragen stellt, wie ist der Wert gerade und dann alle ungerade Werte von vornherein aussortiert. Aber das würde im Moment ein wenig zu weit führen, ist aber perfekt für Wetten geeignet: "Denk dir eine Zahl zwischen 1 und einer Million aus, ich wette um 20 € , dass ich nicht mehr als 20 Schritte brauchen werde die Zahl zu erraten!) , Bei etwaigen Einnahmen durch diesen Tipp, bitte ich darum 10% an diese Webseite zu spenden ;-)

Probiert ein wenig mit der Binärsuche herum, ich werde demnächst eine Binärsuche Klasse erstellen, welche sich perfekt in jedes Programm integrieren wird und hier als frei verfügbarer Download erscheint.

Somit einfach mal wieder hereinschauen, damit man auf dem laufenden bleibt!