Binäre Suche

Funktionsweise der binären Suche

Die binäre Suche ist ein effizienter Algorithmus zum Auffinden eines Elements in einer sortierten Liste.

Voraussetzungen

• Die Liste oder das Array muss sortiert sein.
• Der Algorithmus vergleicht das gesuchte Element mit dem mittleren Element des aktuellen Suchbereichs.

Ablauf

1. Bestimme die Mitte des Suchbereichs.
2. Vergleiche das mittlere Element mit dem gesuchten Wert.
3. Bei Gleichheit: Suche erfolgreich beendet.
4. Ist der gesuchte Wert kleiner: Suche im linken Teil weiter.
5. Ist der gesuchte Wert größer: Suche im rechten Teil weiter.
6. Wiederhole, bis das Element gefunden ist oder der Suchbereich leer ist.

Code

public class BinareSuche {
    public static int binareSuche(int[] array, int zielwert) {
        int links = 0;
        int rechts = array.length - 1;

        while (links <= rechts) {
            int mitte = links + (rechts - links) / 2;

            if (array[mitte] == zielwert) {
                return mitte; // Element gefunden
            }

            if (array[mitte] < zielwert) {
                links = mitte + 1; // Rechter Teil
            } else {
                rechts = mitte - 1; // Linker Teil
            }
        }
        return -1; // Element nicht gefunden
    }

    public static void main(String[] args) {
        int[] zahlen = {2, 4, 7, 10, 15, 20};
        int ergebnis = binareSuche(zahlen, 10);
        
        if (ergebnis != -1) {
            System.out.println("Wert gefunden an Index: " + ergebnis);
        } else {
            System.out.println("Wert nicht gefunden.");
        }
    }
}   

Gut zu wissen

• Effizienz: Zeitkomplexität $O(\log n)$.
• Voraussetzung: Sortierte Daten.
• Anwendung: Ideal für große, sortierte Arrays.