Das binäre Suchen ist wieder ein Rekursionsverfahren. Dabei muss das Feld allerdings sortiert sein (deshalb ist in unserem Beispiel-Applet mit dem Zufallsfeld auch zusätzlich der Quicksort implementiert).
Es wird wieder ein Pivot-Element ermittelt ("linke Mitte"). Ist das Suchelement kleiner als das Pivotelement, wird rekursiv in der linken Hälfte weitergemacht, ist das Suchelement grösser als das Pivotelement wird in der rechten Hälfte weitergemacht.
Sobald die Länge des Suchfeldes 1 ist, ist die Rekursion beendet. Entweder enthält es das Suchelement oder nicht.
Basis ist hier die rekursive Methode suche:
public boolean suche(int suchbegriff,int min, int max)
{
int pivot;
boolean gefunden = false;
pivot=(min+max)/2;
if (feld[pivot]==suchbegriff)
{
gefunden=true;
index=pivot;
}
if(!gefunden && (min<max))
{
if(feld[pivot]>suchbegriff)
gefunden=suche(suchbegriff,min,pivot-1);
else
gefunden=suche(suchbegriff,pivot+1,max);
}
return gefunden;
}
Es werden neben dem Suchbegriff die Feldgrenzen min und max übergeben, die die Ränder des Suchbereichs markieren. Wenn der Suchbegriff an der Pivotstelle liegt, ist die Rekursion beendet (gefunden wird auf true gesetzt). Ist min<max (sprich die Länge des Suchbereichs größer als 1), dann beginnt die mögliche Rekursion.
Dann muss geschaut werden, in welcher Hälfte der Suchbegriff liegt. Entsprechend wird dann suche rekursiv im linken oder rechten Bereich aufgerufen.
Sofern es sich wieder nicht um elementare Datentypen handelt, müssen der Vergleich durch einen Aufruf der equals-Methode und die Größer-/Kleiner-Beziehungen durch eigene Implementierungen von Methoden less bzw. greater realisiert werden.
Implementieren Sie die Binäre Suche inklusive eines Quicksorts für 50 zufällige Feldelemente.
© Ralph-Erich Hildebrandt, 02. November 2015