Wenn Sie die Übungen der Folge 11 (Vokabelliste) erfolgreich bearbeitet haben, kennen Sie das Prinzip der linearen Suche bereits. In einer Liste deutsch/englischer Vokabeln sollte ein deutscher Begriff gesucht werden, beispielsweise "Hund", um anschließend die englische Übersetzung "dog" auszugeben. Die Vokabeln waren in der ArrayList nicht sortiert, sondern standen in der Reihenfolge ihrer Eingabe.
public Vokabel sucheDeutsch(String deutsch)
{
for (int i = 0; i < liste.size(); i++)
{
Vokabel v = liste.get(i);
if (v.getDeutsch().equalsIgnoreCase(deutsch))
return v;
}
return null;
}
Die lineare Suche beginnt beim ersten Element der ArrayList, also beim Index 0. Mit der Methode get(i) werden die Vokabeln nacheinander aus der Liste abgerufen und jeweils in der lokalen Variablen v gespeichert.
Der Aufruf v.getDeutsch() liefert das deutsche Wort als String zurück. Mit der String-Methode equalsIgnoreCase(deutsch) wird dieses Wort mit dem Suchbegriff verglichen, wobei die Groß- und Kleinschreibung ignoriert wird. Stimmen beide Wörter überein, liefert der Vergleich den Wert true, und die gefundene Vokabel wird mit return zurückgegeben. Damit ist die Suche beendet.
Wurde die gesamte ArrayList erfolglos durchsucht, ist die gesuchte Vokabel nicht vorhanden. In diesem Fall liefert die Methode den Wert null zurück.
Definition: Lineare Suche
Bei der linearen Suche werden die Elemente einer Datenmenge nacheinander überprüft, beginnend mit dem ersten Element. Die Suche endet, sobald
- das gesuchte Element gefunden wurde oder
- alle Elemente erfolglos überprüft worden sind.
Beachten Sie, dass diese Definition keine Hinweise auf eine konkrete Implementierung enthält. Sie beschreibt lediglich das Prinzip des Algorithmus, der in jeder beliebigen Programmiersprache umgesetzt werden kann.
Übungen
Ein Schüler hat einen Entwurf für eine Java-Methode erstellt, die in einem Objekt-Array CD[] nach einem bestimmten Begriff sucht. Falls die gesuchte CD gefunden wurde, soll der Titel der CD ausgegeben werden. Wurde die CD nicht gefunden, soll ein entsprechender Hinweis ausgegeben werden.
Hier das Flussdiagramm des Schülers für den linearen Suchalgorithmus:
Ein Flussdiagramm für eine lineare Suche
Autor: Ulrich Helmich 2016, Lizenz: Public domain.
Analysieren Sie diesen Entwurf und beurteilen Sie, ob er funktionieren könnte. Falls Sie Fehler finden, verbessern Sie den Entwurf.
Lösungsvorschlag auf den Seiten für Lehrer(innen) / Nähere Infos dazu
Systematische Untersuchung der linearen Suche
Um das Zeitverhalten verschiedener Suchverfahren zu untersuchen, verwenden wir ein einfaches Modellsystem: ein Array aus zwölf unsortierten ganzen Zahlen. Statt mit umfangreichen Bücher- oder CD-Sammlungen zu arbeiten, können wir so die einzelnen Suchschritte leicht nachvollziehen.
Vorgehen
Die folgende Tabelle zeigt zwölf unsortierte Zahlen zwischen 1 und 17. Jede Zahl kommt genau einmal vor. In der oberen Zeile stehen die Zahlen, in der unteren Zeile die zugehörigen Array-Indizes.
| 17 | 3 | 8 | 12 | 4 | 16 | 2 | 9 | 7 | 6 | 11 | 15 |
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
Wir simulieren nun die lineare Suche nach sechs verschiedenen Zahlen und zählen jeweils, wie viele Vergleiche mit Array-Elementen notwendig sind.
Ergebnisse
Gesucht werden nacheinander die Zahlen 1, 3, 6, 9, 12 und 13.
- 1: Nicht vorhanden – 12 Vergleiche.
- 3: Steht an Index 1 – 2 Vergleiche.
- 6: Steht an Index 9 – 10 Vergleiche.
- 9: Steht an Index 7 – 8 Vergleiche.
- 12: Steht an Index 3 – 4 Vergleiche.
- 13: Nicht vorhanden – 12 Vergleiche.
Insgesamt benötigen wir also 12 + 2 + 10 + 8 + 4 + 12 = 48 Vergleiche. Teilen wir diese Summe durch die sechs Suchvorgänge, erhalten wir einen Durchschnitt von 8 Vergleichen pro Suche.
Dieses Ergebnis zeigt eine wesentliche Eigenschaft der linearen Suche: Je weiter hinten sich ein gesuchtes Element befindet, desto mehr Vergleiche sind notwendig. Ist die Suchzahl nicht vorhanden, muss sogar das gesamte Array durchsucht werden.
Bei größeren Arrays steigt daher auch die durchschnittliche Anzahl der Vergleiche. Wie stark dieser Anstieg ausfällt, wollen wir nun mit einem Java-Programm untersuchen.
Schreiben Sie eine Java-Klasse, die folgende Instanzvariablen und Methoden besitzt:
- Ein int-Array mit 100 Elementen.
- Eine Methode, die das Array mit 100 Zufallszahlen zwischen 1 und 500 füllt. Zahlen dürfen dabei mehrfach vorkommen.
- Eine Methode, die eine Zahl im Array sucht und die Anzahl der notwendigen Vergleiche als int-Wert zurückliefert. Wird die Suchzahl nicht gefunden, liefert die Methode den Wert 100 zurück.
- Eine Methode, die 100 zufällige Suchzahlen zwischen 1 und 500 erzeugt und für jede Zahl die Suchmethode aufruft. Die Anzahl der Vergleiche wird aufsummiert. Anschließend wird der Durchschnitt berechnet und als double-Wert in der Konsole ausgegeben.
Lösungsvorschlag auf den Seiten für Lehrer(innen) / Nähere Infos dazu
Ist die lineare Suche in einem sortierten Array schneller?
Man könnte vermuten, dass die lineare Suche in einem sortierten Array schneller ist als in einem unsortierten. Das ist aber nicht unbedingt der Fall. Wenn wir beispielsweise nach der größten Zahl suchen, die ganz hinten im sortierten Array steht, müssen wir trotzdem alle Elemente überprüfen.
Ist die gesuchte Zahl vorhanden und kann sie mit gleicher Wahrscheinlichkeit an jeder Position stehen, benötigt die lineare Suche bei einem Array mit n Elementen durchschnittlich (n + 1) / 2 Vergleiche. Dabei spielt es keine Rolle, ob das Array sortiert ist oder nicht.
Wenn allerdings nach Zahlen gesucht wird, die nicht im Array enthaltenen sind, ist die lineare Suche in einem sortierten Array schneller als in einem unsortierten. Sobald im sortierten Array eine Zahl gefunden wird, die größer ist als die Suchzahl, kann die Suche abgebrochen werden. Bei einem unsortierten Array müsste man dagegen alle Elemente untersuchen.
Seitenanfang -
Weiter mit der binären Suche...