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:

    Erstes Struktogramm (Versuch) zur Linearen Suche

    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!

    Struktogramm: Lineare Suche

    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!

    Scratch: Barbarenszenario

    Das Einlesen der Antwort wurde bereits programmiert. Die Eingabe des Benutzers wird in der Variablen gesuchtesElement gespeichert. Entwerfen Sie den Programmcode hier:

    Scratch:Unterprogramm (leer) zur Linearen Suche

    (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!

    Scratch: Roboter-Szenario

    Das Einlesen des Gegenstandes wurde bereits programmiert. Die Eingabe des Benutzers wird in der Variablen gesuchtesElement gespeichert. Entwerfen Sie den Programmcode hier:

    Scratch:Unterprogramm (leer) zur Linearen Suche

    Erklärvideo: Lineare Suche

    Arbeitsblatt: Lineare Suche

    Arbeitsblatt »Lineare Suche« (PDF)

    Copyright © 2020Powered by Bludit