Eine binäre Suche beruht darauf, dass ein sortiertes
Arrays daraufhin untersucht wird, ob sich der gesuchte Wert in der ersten
oder zweiten Hälfte befindet. Nach der Entscheidung darüber wird
der gewählte Bereich wiederum unterteilt, ein Teilbereich gewählt,
etc.
Im gewählten Beispiel wird innerhalb der main-Methode ein Array
deklariert und mit int-Werten initialisiert. Da die Suche über einen
Größenvergleich der Werte abläuft, muss das Array
anschließend zwingend sortiert werden. Der Methode searchBinary()
werden vier Parameter übergeben:
- das Array selbst
- der Startindex der Suche
- der Schlussindex der Suche
- die gesuchte Zahl
import java.util.Arrays;
public class BinarySearch {
public void searchBinary(int[] intArr, int anfang, int ende, int zahl) {
int grenze = anfang + ((ende - anfang) / 2);
if (intArr.length == 0) {
System.out.println("Array leer.");
return;
}
if (grenze >= intArr.length){
System.out.println(zahl + " nicht im Array enthalten.");
return;
}
if (zahl > intArr[grenze]) {
searchBinary(intArr, grenze + 1, ende, zahl);
} else if (zahl < intArr[grenze] && anfang != grenze) {
searchBinary(intArr, anfang, grenze - 1, zahl);
} else if(zahl == intArr[grenze]) {
System.out.println(zahl + " an Position " + grenze + " enthalten.");
} else{
System.out.println(zahl + " nicht im Array enthalten.");
}
}
public static void main(String[] args) {
int[] testArr = { 5, 3, 5, 228, 14, 69, 18, 27, 109, 85 };
Arrays.sort(testArr);
BinarySearch bs = new BinarySearch();
bs.searchBinary(testArr, 0, testArr.length - 1, 228);
}
}
Die Methode wird rekursiv durchlaufen. Nach zwei Sicherheitsprüfungen
der Länge des übergebenen Arrays und der Größe des
errechneten Mittelwertes werden hierzu die Werte des Start- und
Schlussindexes beim rekursiven Aufruf neu belegt und aus ihnen ein
Mittelwert berechnet, der zur Aufteilung des Arrays oder, in weiteren
Durchläufen, seinen Teilabschnitten dient.
Auf diese Weise wird
jedes Mal entschieden, ob der gesuchte Wert kleiner oder größer
ist als derjenige an der Position des errechneten Mittelindexes. Ist eines
von beidem der Fall, so wird die Methode mit neuen Werten für den
Anfangs- und Schlussindex erneut aufgerufen, wieder der Mittelindex
berechnet, etc. Nach Abschluss der Unterteilungsdurchläufe entspricht
der gesuchte Wert entweder demjenigen des zuletzt ermittelten Mittelindex
oder er ist im Array gar nicht vorhanden.
Algorithmen
