Lineare Suche
Etwas in einer Menge von Daten zu finden ist die vielleicht häufigste Aufgabe der Informatik überhaupt. Das einfachste Verfahren dafür kennst du schon – jetzt schauen wir es uns genau an.
Das Verfahren
Die lineare Suche (auch: sequenzielle Suche) durchläuft das Feld von vorne nach hinten und vergleicht jeden Wert mit dem gesuchten. Beim ersten Treffer bricht sie ab.
Wird das Ende erreicht, ohne dass etwas gefunden wurde, kommt der Wert nicht vor.
Als Struktogramm:
┌──────────────────────────────────────────────┐
│ für i von 0 bis werte.length - 1 │
│ ┌────────────────────────────────────────┐ │
│ │ werte[i] = gesucht │ │
│ │ ja ╱──────────╲ nein │ │
│ ├─────────────────────────┬──────────────┤ │
│ │ gib i zurück │ ∅ │ │
│ └─────────────────────────┴──────────────┘ │
├──────────────────────────────────────────────┤
│ gib -1 zurück │
└──────────────────────────────────────────────┘Wie viele Vergleiche braucht das?
Ein Feld hat 100 Einträge. Wie viele Vergleiche macht die lineare Suche
a) im besten Fall,
b) im schlechtesten Fall,
c) im Durchschnitt, wenn der gesuchte Wert enthalten ist?
Und: Was ist eigentlich der schlechteste Fall?
Auflösung
a) 1 – wenn der gesuchte Wert gleich vorne steht.
b) 100 – wenn er ganz hinten steht oder gar nicht vorkommt. Der Fall „nicht enthalten“ ist der eigentlich schlimme: Da hilft kein Glück.
c) Im Mittel etwa 50. Wenn der Wert gleich wahrscheinlich an jeder Stelle steht, ist der Durchschnitt (1 + 2 + … + 100) / 100, also 50,5.
Der entscheidende Punkt: Verdoppelt sich die Anzahl der Einträge, verdoppelt sich auch die Anzahl der Vergleiche. Man sagt: Der Aufwand wächst linear – daher der Name.
Vergleiche zählen statt Sekunden messen
Wie schnell ein Programm läuft, hängt vom Rechner ab. Wie viele Vergleiche ein Algorithmus macht, hängt nur vom Algorithmus ab. Deshalb zählt man in der Informatik Operationen, nicht Sekunden.
a) Führe das Programm aus. Bestätigt sich, dass sich die Vergleiche mit der Feldgröße verdoppeln?
b) Erweitere das Programm um Felder der Größe 400, 800 und 1600. Trage die Ergebnisse in eine Tabelle ein.
c) Was ändert sich, wenn der gesuchte Wert enthalten ist? Probiere es aus, indem du gezielt nach feld[0] und nach dem letzten Eintrag suchst.
Aufgabe 1: Suche mit Rückmeldung
Erweitere die lineare Suche so, dass alle Tests grün werden. Beachte besonders die Sonderfälle.
Tipp 1: letzterIndex
Zwei Wege führen zum Ziel:
- Von hinten nach vorne suchen und beim ersten Treffer zurückgeben.
- Von vorne suchen, aber nicht abbrechen, sondern den Index in einer Variablen merken und weitersuchen.
Beide sind richtig. Der erste ist im Schnitt schneller, der zweite braucht keine Rückwärtsschleife.
Tipp 2: enthaelt
Du hast ersterIndex bereits. Nutze sie – Methoden dürfen einander aufrufen.
Aufgabe 2: Suche in einem sortierten Feld
Angenommen, das Feld ist bereits aufsteigend sortiert: {1, 3, 4, 7, 9, 12, 15}.
a) Bei der Suche nach der 5 kann man früher abbrechen als bei einem unsortierten Feld. Erkläre, wann und warum.
b) Ändere die Suchmethode entsprechend.
c) Um wie viel schneller wird die Suche dadurch im schlechtesten Fall? Denk gut nach, bevor du antwortest.
Auflösung
a) Sobald ein Wert größer als der gesuchte auftaucht, kann der gesuchte nicht mehr kommen – hinter ihm stehen ja nur noch größere. Bei der Suche nach 5 bricht man also schon bei der 7 ab, nach vier Vergleichen statt sieben.
b)
for (int i = 0; i < pWerte.length; i++) {
if (pWerte[i] == pGesucht) {
return i;
}
if (pWerte[i] > pGesucht) {
return -1;
}
}
return -1;c) Im schlechtesten Fall gar nicht. Wer nach einem Wert sucht, der größer als alle im Feld ist, muss weiterhin alle durchlaufen. Der Aufwand bleibt linear – nur der Durchschnitt halbiert sich ungefähr.
Dass ein sortiertes Feld sehr viel mehr hergibt, siehst du im Lernpfad Erweiterungen bei der binären Suche: Die kommt bei 1000 Einträgen mit zehn Vergleichen aus – nach demselben Prinzip wie bei den Goldmünzen.
Zusatzaufgabe
Visualisiere die lineare Suche mit Scratch for Java:
Zeichne die Werte als Säulen. Lass die Suche schrittweise laufen und färbe die gerade geprüfte Säule ein. Wird der Wert gefunden, färbe die Säule grün.
Nutze SystemTools.pause(200), damit man dem Verfahren zusehen kann. Und setze speed nicht hoch – hier soll es ja langsam sein.