Binäre Suche: Die Startaufstellung

Lösung geprüft

Die Aufgabe der heutigen Stunde ist die binäre Suche an einem konkreten Beispiel! Bastians Fußballmannschaft, ein sortiertes Array mit Trikotnummern, und die Frage: ist eine bestimmte Nummer aufgestellt? Hier führen wir den Algorithmus einmal von Hand aus – genau das wird in der Klausur verlangt.

Die Aufgabenstellung lautet

In Bastians Fußballmannschaft hat jeder Spieler seine eigene Trikotnummer. Sein Fußballtrainer speichert die Startaufstellungen für die jeweiligen Spiele jeweils in einem sortierten Array. Für das kommende Spiel hat er die folgenden Trikotnummern ausgewählt. Bastian hat die Trikotnummer 7.

a) Führen Sie den Algorithmus der binären Suche auf dem Array aus, um zu prüfen, ob Bastian aufgestellt ist. Notieren Sie für jeden Schritt die Werte der Variablen links, mitte und rechts.
b) Führen Sie den Algorithmus der binären Suche auf dem Array aus, um zu prüfen, ob der Spieler mit der Trikotnummer 17 aufgestellt ist. Notieren Sie auch hier für jeden Schritt die Werte.
c) Rechnerarbeit: Implementieren Sie das Spielerarray in einer Klasse Aufstellung. Implementieren Sie eine Methode public boolean istAufgestellt(int Trikotnummer), die true zurückgibt, wenn der Spieler mit der Trikotnummer aufgestellt ist und ansonsten false.

Das Array

Index	[0]	[1]	[2]	[3]	[4]	[5]	[6]	[7]	[8]	[9]	[10]
Nummer	1	3	5	7	8	10	11	13	14	16	19

Wichtig ist, dass das Array sortiert ist. Ohne das funktioniert die binäre Suche nicht – sie würde ganze Bereiche wegwerfen, in denen die gesuchte Zahl noch liegen könnte.

flowchart TD
    A["links = 0, rechts = Länge des Arrays - 1"] --> B{"links <= rechts?"}
    B -- nein --> Z["return false"]
    B -- ja --> C["mitte = (links + rechts) / 2"]
    C --> D{"aktuelles Element gleich Suchschlüssel?"}
    D -- WAHR --> T["return true"]
    D -- FALSCH --> E{"aktuelles Element < Suchschlüssel?"}
    E -- WAHR --> F["links = mitte + 1"]
    E -- FALSCH --> G{"aktuelles Element > Suchschlüssel?"}
    F --> G
    G -- WAHR --> H["rechts = mitte - 1"]
    G -- FALSCH --> B
    H --> B

Wie die binäre Suche den Bereich halbiert

Das ist der Ablauf, den wir gleich zweimal von Hand durchspielen. Die drei Abfragen kommen im Struktogramm nacheinander und nicht als else-Kette – das wird später bei der Aufgabe wichtig, in der man die Zeilen sortieren soll.

a) Die Suche nach der 7

Durchlauf	links	mitte	rechts	a[mitte]	Vergleich
1	0	5	10	10	10 > 7 → rechts = 4
2	0	2	4	5	5 < 7 → links = 3
3	3	3	4	7	gefunden → true

Drei Durchläufe für elf Spieler. Die lineare Suche hätte vier gebraucht (Index 0, 1, 2, 3) – der Unterschied ist hier noch klein, weil das Array winzig ist.

Rechnung für die Mitte: mitte = (links + rechts) / 2. Im ersten Durchlauf (0 + 10) / 2 = 5. Im zweiten (0 + 4) / 2 = 2. Im dritten (3 + 4) / 2 = 3,5 – und Java schneidet bei int-Division ab, also 3.

b) Die Suche nach der 17

Durchlauf	links	mitte	rechts	a[mitte]	Vergleich
1	0	5	10	10	10 < 17 → links = 6
2	6	8	10	14	14 < 17 → links = 9
3	9	9	10	16	16 < 17 → links = 10
4	10	10	10	19	19 > 17 → rechts = 9
–	10	links > rechts → Schleife endet, return false

Das ist der interessantere Fall: die 17 ist nicht dabei. Der Suchbereich schrumpft trotzdem bei jedem Schritt, bis links größer als rechts wird. Dann ist der Bereich leer und es gibt nichts mehr zu suchen – die Methode gibt false zurück.

Genau daran erkennt man in der Klausur, ob jemand den Algorithmus verstanden hat: die Abbruchbedingung solange links <= rechts ist das, was den Nicht-gefunden-Fall überhaupt beendet. Ohne sie läuft die Schleife ewig.

c) Die Klasse Aufstellung

Aufstellung.java

/* meininfokurs.cmrg.site */

/**
 *
 * Binaere Suche auf der Startaufstellung
 *
 * @version 1.0 vom 14.09.2025
 * @meininfokurs.cmrg.site
 */

public class Aufstellung {

    // Das Array MUSS sortiert sein, sonst funktioniert die binaere Suche nicht
    private int[] spieler = {1, 3, 5, 7, 8, 10, 11, 13, 14, 16, 19};

    /**
     * Prueft mit binaerer Suche, ob ein Spieler aufgestellt ist.
     *
     * @param Trikotnummer die gesuchte Nummer
     * @return true, wenn der Spieler aufgestellt ist, sonst false
     */
    public boolean istAufgestellt(int Trikotnummer) {
        int links = 0;
        int rechts = spieler.length - 1;
        int mitte;

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

            if (spieler[mitte] == Trikotnummer) {
                return true;
            } else if (spieler[mitte] < Trikotnummer) {
                links = mitte + 1;
            } else {
                rechts = mitte - 1;
            }
        } // end of while

        return false;
    }

    public static void main(String[] args) {
        Aufstellung a = new Aufstellung();
        System.out.println("Nummer 7  aufgestellt? " + a.istAufgestellt(7));
        System.out.println("Nummer 17 aufgestellt? " + a.istAufgestellt(17));
        System.out.println("Nummer 1  aufgestellt? " + a.istAufgestellt(1));
        System.out.println("Nummer 19 aufgestellt? " + a.istAufgestellt(19));
    } // end of main

} // end of class Aufstellung

Die drei Stellen, an denen es schiefgeht

1. rechts = spieler.length - 1, nicht spieler.length. Das Array hat elf Einträge, der letzte Index ist aber 10. Ohne das -1 greifst du im ersten Durchlauf schon daneben.

2. links <= rechts, nicht links < rechts. Mit dem kleineren Zeichen wird der Fall links == rechts nicht mehr geprüft – und das ist genau der letzte verbliebene Eintrag. Suchst du die 19 (Index 10), findet die Methode sie dann nicht, obwohl sie drin ist. Der Fehler fällt bei den meisten Tests nicht auf, nur bei den Rändern.

3. mitte + 1 und mitte - 1, nicht einfach mitte. Die Mitte wurde ja gerade geprüft und passte nicht, also darf sie raus aus dem Suchbereich. Schreibst du links = mitte, kann sich der Bereich irgendwann nicht mehr verkleinern und die Schleife läuft endlos.

Und so sieht es aus

Konsole

Nummer 7  aufgestellt? true
Nummer 17 aufgestellt? false
Nummer 1  aufgestellt? true
Nummer 19 aufgestellt? true

Die letzten beiden Tests sind absichtlich die Ränder: der erste und der letzte Eintrag. Wenn deine Methode bei denen false sagt, hast du Fehler 1 oder Fehler 2 von oben drin.