Q1 / Suchen und Sortieren

Suchen: iterativ und rekursiv

Lösung geprüft

Die Aufgabe der heutigen Stunde ist Suchen – iterativ und rekursiv! Fünf Teilaufgaben, und diesmal geht es nicht mehr nur um Arrays, sondern auch um die lineare Liste mit ihren toFirst()-, hasAccess()- und next()-Methoden. Die kommt im Abi ständig vor, deshalb lohnt es sich, das Muster einmal richtig zu verstehen.

Aufgabe 1 – Das Musikverwaltungsprogramm

Das Muster für lineare Listen

Bevor es losgeht: fast jede Aufgabe mit einer linearen Liste sieht gleich aus. Man merkt sich diese vier Zeilen und kommt damit sehr weit:

liste.toFirst();                   // an den Anfang springen
while (liste.hasAccess()) {        // solange man auf einem Element steht
    Musiktitel mt = liste.getContent();   // aktuelles Element holen
    // ... hier passiert die eigentliche Arbeit ...
    liste.next();                  // ein Element weiter
}

flowchart TD
    A["gefunden = false"] --> B["liste.toFirst(), Zeiger auf das erste Element"]
    B --> C{"liste.hasAccess() UND gefunden == false?"}
    C -- nein --> Z["return gefunden"]
    C -- ja --> D{"liste.getContent() gleich Suchschlüssel?"}
    D -- WAHR --> E["gefunden = true"]
    D -- FALSCH --> F["liste.next(), ein Element weiter"]
    E --> F
    F --> C

hasAccess() ist dabei das Entscheidende: es sagt, ob der Zeiger überhaupt auf einem Element steht. Ist man hinten rausgelaufen, liefert es false und die Schleife endet. Vergisst man liste.next(), läuft die Schleife ewig – das ist der häufigste Fehler bei diesen Aufgaben.

a) titelVorhanden

/**
 *
 * Suche in einer linearen Liste
 *
 * @version 1.0 vom 14.09.2025
 * @meininfokurs.cmrg.site
 */

public boolean titelVorhanden(String pTitel, String pInterpret) {
    liste.toFirst();

    while (liste.hasAccess()) {
        Musiktitel mt = liste.getContent();

        if (mt.getTitel().equals(pTitel)
                && mt.getInterpret().equals(pInterpret)) {
            return true;              // gefunden, sofort raus
        }

        liste.next();
    }

    return false;                     // ganze Liste durch, nichts gefunden
}

Das ist eine lineare Suche auf einer Liste – man muss von vorne durchgehen, weil es bei einer Liste keinen Index gibt, mit dem man in die Mitte springen könnte. Binäre Suche ist auf einer linearen Liste also gar nicht möglich, selbst wenn sie sortiert wäre.

Wichtig: Strings vergleicht man mit .equals() und nicht mit ==. Das == prüft bei Objekten, ob es dasselbe Objekt im Speicher ist – nicht, ob derselbe Text drinsteht. Bei Strings aus Benutzereingaben geht das fast immer schief, und zwar ohne Fehlermeldung. Das Programm findet dann einfach nie etwas.

b) Was methode1 macht

methode1(String pGenre) geht die ganze Liste durch und sammelt alle Musiktitel ein, deren Genre mit dem übergebenen Genre übereinstimmt. Diese hängt sie an eine neue Liste liste2 an und gibt sie am Ende zurück.

Mit anderen Worten: sie filtert die Musiksammlung nach Genre. Ein besserer Name wäre titelNachGenre oder filterGenre – und genau darauf zielt die Aufgabe ab. Man soll merken, dass methode1 ein nichtssagender Name ist und dass man die Funktion trotzdem aus dem Code herauslesen kann.

Zwei Details, die man beim Analysieren erwähnen sollte: die Originalliste wird nicht verändert, es entsteht eine zweite. Und wenn kein Titel passt, kommt eine leere Liste zurück – nicht null. Das ist gut so, weil der Aufrufer dann ohne Sonderprüfung damit weiterarbeiten kann.

Aufgabe 2 – pruefe

/**
 * Die Testergebnisse im Array ergebnisse sollen ueberprueft werden.
 *
 * @param ergebnisse ein Array vom Typ boolean
 * @return true, falls mindestens ein positives Testergebnis vorkommt,
 *         ansonsten false
 */
public boolean pruefe(boolean[] ergebnisse) {
    for (int i = 0; i < ergebnisse.length; i++) {
        if (ergebnisse[i]) {
            return true;
        }
    }
    return false;
}

Wieder das Muster der linearen Suche: beim ersten Treffer sofort true zurückgeben, und erst wenn alles durchlaufen ist, false.

Beachte if (ergebnisse[i]) ohne Vergleich. Der Eintrag ist schon ein boolean, man muss ihn nicht erst mit true vergleichen. if (ergebnisse[i] == true) funktioniert zwar auch, ist aber umständlich – und wer sich dabei vertippt und = statt == schreibt, hat einen Fehler, den man schwer sieht.

Aufgabe 3 – Die Logistik mit zwei Lagern

public boolean suche(int Artikelnummer) {
    if (sucheInLager(lager1, Artikelnummer)) {
        return true;
    }
    return sucheInLager(lager2, Artikelnummer);
}

// Hilfsmethode, damit der Code nicht zweimal dasteht
private boolean sucheInLager(List<Artikel> lager, int Artikelnummer) {
    lager.toFirst();
    while (lager.hasAccess()) {
        if (lager.getContent().getArtikelnummer() == Artikelnummer) {
            return true;
        }
        lager.next();
    }
    return false;
}

Der Kniff hier ist die Hilfsmethode. Man könnte die Suchschleife zweimal hinschreiben, einmal für lager1 und einmal für lager2 – das wären dann zwei fast identische Blöcke, und wenn man später einen Fehler findet, muss man ihn an zwei Stellen beheben.

Möglich ist das, weil lager1 und lager2 denselben Typ haben. Die Hilfsmethode bekommt einfach die Liste als Parameter übergeben.

Und hier steht == statt .equals() – das ist richtig so, weil die Artikelnummer ein int ist und kein String. Bei einfachen Datentypen vergleicht == tatsächlich die Werte.

Aufgabe 4 – Binäre Suche auf den Quadratzahlen

a) Die Suche nach der 100

Vier Aufrufe. Der letzte ist der wichtige: links und rechts sind beide 9, der Bereich besteht also nur noch aus einem Element – und das ist der gesuchte Wert.

b) Die Suche nach der 10

Die 10 ist keine Quadratzahl, also kann sie gar nicht drin sein. Der Algorithmus engt trotzdem sauber ein und landet genau in der Lücke zwischen 9 und 16.

Aufgabe 5 – Die Zeilen sortieren

/**
 *
 * Binaere Suche, iterativ - die Zeilen in der richtigen Reihenfolge
 *
 * @version 1.0 vom 14.09.2025
 * @meininfokurs.cmrg.site
 */

public boolean binaereSuche_iterativ(int[] a, int i) {
    int links, mitte, rechts;
    links = 0;
    rechts = a.length - 1;

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

        if (a[mitte] == i) {
            return true;
        }
        if (a[mitte] < i) {
            links = mitte + 1;
        }
        if (a[mitte] > i) {
            rechts = mitte - 1;
        }
    }

    return false;
}

Warum genau diese Reihenfolge

1. mitte = (int)((rechts + links) / 2); muss ganz oben in der Schleife stehen. Erst wenn die Mitte für den aktuellen Bereich berechnet ist, kann man dort hineinschauen.
2. if (a[mitte] == i) return true; kommt als Nächstes. Trifft man den Wert, ist man fertig und braucht die anderen Vergleiche nicht mehr.
3. if (a[mitte] < i) links = mitte + 1; – der gesuchte Wert liegt rechts, also rückt die linke Grenze nach.
4. if (a[mitte] > i) rechts = mitte - 1; – umgekehrt.

Die ergänzten Klammerungen sind die geschweiften Klammern nach jedem if und die Klammern um den ganzen Schleifenrumpf. Bei einzeiligen if-Anweisungen darf man sie in Java weglassen, aber genau dann passiert der Klassiker: man fügt später eine zweite Zeile hinzu und die gehört plötzlich nicht mehr zum if.