Lernfabrik

Einführung in das Sequentielle Suchen

Sequentielles Suchen

Das sequentielle Suchen (auch lineares Suchen genannt) ist ein einfacher Suchalgorithmus, bei dem jedes Element einer Liste nacheinander überprüft wird, bis das gesuchte Element gefunden wurde oder das Ende der Liste erreicht ist.

Dieser Algorithmus funktioniert unabhängig davon, ob die Daten sortiert sind oder nicht. Er eignet sich besonders für kleine Datenmengen oder unstrukturierte Daten.

Grundlagen für das Sequentielle Suchen

Voraussetzung: Kenntnisse über Arrays sind vorhanden.
Eine der häufigsten Aufgaben in der Informatik ist das Suchen von Daten.
Ein einfacher Startpunkt ist das Suchen in (un-)sortierten Folgen.

Vergleichszahlen bei erfolgreicher Suche:

Bester Fall: 1 Vergleich
Durchschnitt: n / 2
Schlechtester Fall: n

Vergleichszahlen bei erfolgloser Suche:

Immer: n Vergleiche notwendig
Komplexität: O(n)

Die Laufzeitkomplexität beim sequentiellen Suchen beträgt im Worst-Case O(n), da im schlimmsten Fall alle n Elemente überprüft werden müssen.

Beispiel: Sequentielle Suche

Gegeben: Liste [4, 8, 15, 16, 23, 42]

Gesucht: 23

Durchlauf: 4 → 8 → 15 → 16 → 23

Übungsaufgaben

Hinweis: Die Lösung Ihrer Aufgabe muss in Moodle hochgeladen werden.

Aufgabe: Sequentielles Suchen

Schwierigkeitsgrad: Einfach

Gegeben sei die Liste:

Suche nach der Zahl 14 mithilfe des sequentiellen Suchalgorithmus.
Wie viele Vergleiche werden im schlechtesten Fall benötigt?

Programmieraufgabe: Sequentielles Suchen

Schwierigkeitsgrad: Mittel

Gegeben sei ein Array mit folgenden Werten:

Schreiben Sie eine Funktion fLinearSuche(), die überprüft, ob ein bestimmter Wert im Array enthalten ist.
Geben Sie zusätzlich die Anzahl der benötigten Vergleiche aus.