Binäre Suche

Ein Hotel speichert die Nummern seiner belegten Zimmer aufsteigend sortiert. Ist Zimmer 135 belegt? Ein Blick in die Mitte verrät, in welcher Hälfte man weitersuchen muss.

• Voraussetzung:die Reihung ist sortiert — sonst sagt die Mitte nichts über die Hälften.
• Suchbereich:die Indizes von links bis rechts; zu Beginn 0 bis Länge − 1.
• Mitte:mitte = (links + rechts) / 2 mit ganzzahliger Division, z. B. \((0 + 10) / 2 = 5\), \((6 + 7) / 2 = 6\).
• Treffer:a[mitte] = x — Index mitte zurückgeben.
• Zu klein:a[mitte] < x — rechts weitersuchen: links ← mitte + 1.
• Zu groß:a[mitte] > x — links weitersuchen: rechts ← mitte − 1.
• Abbruch:gilt links > rechts, ist der Bereich leer — Rückgabe −1.

static int binaereSuche(int[] a, int x) {
    int links = 0;
    int rechts = a.length - 1;
    while (links <= rechts) {
        int mitte = (links + rechts) / 2;   // ganzzahlige Division
        if (a[mitte] == x) {
            return mitte;
        } else if (a[mitte] < x) {
            links = mitte + 1;              // x kann nur rechts liegen
        } else {
            rechts = mitte - 1;             // x kann nur links liegen
        }
    }
    return -1;                              // Bereich leer: links > rechts
}

Aufruf binaereSuche(zimmer, 135). Als ein Vergleich zählt jeder Blick auf a[mitte].

• Ergebnis:Index 7 nach 4 Vergleichen — die lineare Suche bräuchte 8.
• Ohne Treffer:die Suche nach 110 endet mit links = 2 > rechts = 1 und liefert −1, ebenfalls nach 4 Vergleichen.
• Halbieren:jeder Vergleich ohne Treffer schließt die Mitte und eine ganze Hälfte aus.

Du steuerst die Suche selbst: Vergleiche das markierte Element in der Mitte mit dem gesuchten Wert und entscheide, welche Hälfte bleibt — die andere wird weggelegt. Klicke dazu in die Hälfte oder nutze die Pfeiltasten. Achte auf die Grenzen links, rechts und mitte.

Halte fest: Jeder Vergleich halbiert den Suchbereich mindestens — bei 15 Elementen ist nach spätestens 4 Vergleichen Schluss, bei 16 nach spätestens 5.