Binäre Suche

Eine binäre Suche beruht darauf, dass ein sortiertes Array 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:

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.

Wenn Ihnen javabeginners.de gefällt, freue ich mich über eine Spende an diese gemeinnützigen Organisationen.