Lineare Suche
Mit unseren digitalen Geräten sind wir eigentlich immer auf der Suche: Wir suchen eine Telefonnummer, ein Bild oder eine MP3-Datei. Unserer Geräte müssen also in der Lage sein, möglichst schnell das Gesuchte zu finden. Um das hinzukriegen, hat man Such-Algorithmen entwickelt, die genau das leisten sollen. Wir schauen uns das am Beispiel des einfachsten Such-Algorithmus an: der linearen Suche.
Algorithmus: Lineare Suche (= sequenzielle Suche)
Die lineare Suche ist die einfachste Suchstrategie, die man eigentlich sofort intuitiv versteht.
Der Algorithmus
Durchlaufe das Array von Anfang bis Ende, bis du das gesuchte Element gefunden hast.
Das war’s. Array durchlaufen. Ist klar. Das heißt dann wohl, dass wir eine Schleife brauchen!
Ein erster Versuch eines Struktogramms könnte so aussehen:
Diese Vorgehensweise müsste eigentlich schon funktionieren, ist aber sehr ineffizient! Das Array wird nämlich immer bis zum Ende durchlaufen, selbst wenn wir das gesuchte Element schon gefunden haben. Viel besser wäre es, wenn wir uns in einer Variable merken würden, ob wir das gesuchte Element gefunden haben. Falls ja, können wir die Schleife abbrechen und damit Zeit sparen.
Damit lösen wir dann auch gleich noch das Problem, dass es nervt, wenn wir bei jedem einzelnen Element eine Ausgabe erhalten, ob es das gesuchte Element ist!
Aufgaben zur Linearen Suche
(1) Gegenstand im Inventar suchen
Öffnen Sie das Projekt 7400-LineareSuche-AUFGABE
Entwerfen Sie in Scratch den Programmcode, mit dem Sie einen Gegenstand im Array suchen können!
Das Einlesen der Antwort wurde bereits programmiert. Die Eingabe des Benutzers wird in der Variablen gesuchtesElement gespeichert. Entwerfen Sie den Programmcode hier:
(2) Roboterspiel: Gegenstand im Inventar suchen
Öffnen Sie das Projekt 7410-LineareSuche-AUFGABE
Entwerfen Sie in Scratch den Programmcode, mit dem Sie einen Gegenstand im Inventar suchen können!
Das Einlesen des Gegenstandes wurde bereits programmiert. Die Eingabe des Benutzers wird in der Variablen gesuchtesElement gespeichert. Entwerfen Sie den Programmcode hier:
(3) Struktogramm zur linearen Suche bauen
Die Polizei hat alle Verkehrssünder/innen in einem Array suender gespeichert. Aktuell enthält das Array die Elemente kilthau, metz, trump, musk. Entwerfen Sie ein Struktogramm, das folgende Anforderungen erfüllt:
- Das Array
suendermuss deklariert und mit den vorgegebenen Werten befüllt werden. - Nach Eingabe eines Namens wird ausgegeben "Sünder gefunden" oder "Sünder nicht gefunden".
Erklärvideo: Lineare Suche
Arbeitsblatt: Lineare Suche
Übersicht: Unterrichtsplan Lineare Suche
- Video schauen bis 5:05 (Struktogramm steht)
- Übung: Selbst implementieren an Scratch-Projekt 7400-LineareSuche-AUFGABE - wenn Sie Schwierigkeiten haben (NUR dann!), können Sie das Video weiterschauen, dort wird die Lösung erklärt)
- Struktogramm "Verkehrssünder/innen" entwerfen (siehe oben, Aufgabe 3).