Binäre Suche

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 static 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]) {
            System.out.println(anfang + " " + ende + " " + 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);
        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.