Lineare Suche

Grundidee - unsortierte Liste

Wir gehen zunächst davon aus, dass die Liste mit den Datenobjekten nicht sortiert ist.

Fall 1: Das Datenobjekt kommt in der Liste vor.

Fall 2: Das Datenobjekt kommt nicht in der Liste vor.

Grundidee - sortierte Liste

Wir gehen jetzt davon aus, dass die Liste mit den Datenobjekten aufsteigend sortiert ist.

Fall 1: Das Datenobjekt kommt in der Liste vor.

Fall 2: Das Datenobjekt kommt nicht in der Liste vor.

Aufgabe 1

Erläutere die Vorgehensweise bei der linearen Suche anhand der Abbildungen. Gehe dabei auch auf den Unterschied zwischen einer unsortierten und einer vorsortierten Liste ein.

Ablaufmodellierung

Die Idee der linearen Suche in einer unsortierten Liste ist sehr einfach: Man durchläuft schrittweise die Liste und vergleicht das vorgegebene Datenobjekt mit jedem Listenelement, bis das entsprechende Datenobjekt in der Liste gefunden ist oder die Liste komplett durchlaufen ist und kein entsprechendes Datenobjekt gefunden wurde.

Der Ablauf lässt sich so präzisieren:

ALGORITHMUS linearesuche_unsortiert
Übergabe: Datenobjekt; Liste
setze indexErgebnis auf -1
setze gefunden auf False
setze index auf 0
SOLANGE index im erlaubten Indexbereich und 
        das Datenobjekt nicht gefunden ist:
    WENN das Datenobjekt mit dem Listenelement zum index übereinstimmt:
        setze gefunden auf True
        setze indexErgebnis auf index
    SONST:
        erhöhe index um 1
Rückgabe: indexErgebnis

Aufgabe 2

Formuliere analog den Algorithmus linearesuche_sortiert.

Aufgabe 3

Implementiere die Algorithmen und teste die entwickelten Programme.