Die Lineare Suche ist ein Such-Algorithmus, der die Elemente einer Liste der Reihe nach (sequenziell) durchläuft, um einen Suchwert x (Schlüssel) zu finden.
Schrittfolge des Algorithmus
Die Suche startet beim ersten Element des Arrays beim Index 0 und läuft solange durch die Liste bis x gefunden wurde. Wenn der Wert x gleich A[ i ] ist, wird der Index des Treffers ausgegeben. Wenn der Wert nicht vorhanden ist, läuft der Algorithmus bis zum Ende des Arrays und liefert das Ergebnis -1.
******** Pseudocode sequenzielle Suche ********* For 0 to A.length-1 do if A[i] = x then return i End For return -1
Komplexität des Algorithmus (Laufzeitanalyse)
Best-Case: O(1), Worst Case: O(n), Average Case: (⌊n/2 ⌋)
Die Komplexität der linearen Suche hängt von der Länge der Liste (n) und der Anzahl der Vergleiche ab – also davon, wie oft ein Wert mit dem Suchwert verglichen wird. Im besten Fall steht der Schlüssel gleich am Anfang der Liste (1 Vergleich). Dann hätte der Algorithmus die Komplexität O(1) und würde nach dem ersten Schritt terminieren. Im schlechtesten Fall befindet sich der Schlüssel am letzten Index oder wäre nicht in der Liste vorhanden. Dann wäre die Komplexität O(n), da der Algorithmus das gesamte Array durchlaufen muss und n Vergleiche benötigt. Im Mittel benötigt der Algorithmus ⌊n /2⌋ Vergleiche.
Beispiel 1:
Lineare Suche nach Katze im Array A
Best-Case: O(1), Worst Case: O(n), Average Case: (⌊n/2⌋)
Der Algorithmus sucht sequenziell nach dem Schlüssel Katze im Array A mit den drei Elementen Hund, Katze und Maus. Er beginnt beim ersten Index A[ 0 ], terminiert (bricht ab), sobald der Schlüssel gefunden wurde und gibt den Index des Treffers zurück.
Initialisierung
Suchbereich A [Hund, Katze, Maus]
Suchwert x = Katze
erster Schritt
Suchbereich A [Hund, Katze, Maus]
Eingabe A[i] = A[0] = Hund
Vergleich A[i] mit x: Hund != Katze, false
zweiter Schritt
Suchbereich A [Hund, Katze, Maus]
Eingabe A[i] = A[1] = Katze
Vergleich A[i] mit x: Katze = Katze, true
Der Algorithmus terminiert nach zwei Schritten, da der Wert Katze gefunden wurde. Die Ausgabe ist 1, der Index des Suchwerts.
******** Pseudocode Finde Katze ********* input: A [Hund, Katze, Maus] def x = Katze For 0 to A.length-1 do if A[i] = x then return i End For return -1
Beispiel 2:
Lineare Suche nach Maximum im Array A
Best-Case: O(n), Worst Case: O(n), Average Case: (n)
Der Algorithmus sucht sequenziell nach dem größten Element im Array A mit den Zahlen 1, 2, 3 und 4. Man initialisiert den Suchwert x mit 0 und der Algorithmus beginnt bei Index 1. Er durchläuft die Folge bis zum letzten Wert und speichert den größten gefundene Wert (A[x]). Bei jedem Schritt vergleicht er A[i] mit A[x] und erhöht x, wenn A[i] größer ist als A[x].
Initialisierung
Suchbereich A [1, 2, 3, 4] mit vier Elementen (n = 4)
Suchwert x = 0
Maximum A[x] = A[0] = 1
erster Schritt
Suchbereich A [1, 2, 3, 4]
Eingabe A[i] = A[1] = 2
Vergleich A[i] > A[x] , 2 > 1, true
neues Maximum A[x] = A[1] = 2
zweiter Schritt
Suchbereich A [1, 2, 3, 4]
Eingabe A[i] = A[2] = 3
Vergleich A[i] > A[x] , 3 > 2, true
neues Maximum A[x] = A[2] = 3
dritter Schritt
Suchbereich A [1, 2, 3, 4]
Eingabe A[i] = A[3] = 4
Vergleich A[i] > A[x] , 4 > 3, true
neues Maximum A[x] = A[3] = 4
Der Algorithmus terminiert nach drei Schritten bei A[3] und gibt den letzten Indexwert 3 als Ergebnis zurück. Da er das gesamte Array durchlaufen muss, aber erst bei A[1] beginnt, benötigt er n – 1 = 3 Vergleiche.
******** Pseudocode Finde Maximum ********* input: A [1,2,3,4] def x = 0 For 1 to A.length-1 do if A[i] > A[x] then x = i End For return x
Beispiel 3:
Lineare Suche nach dem größtem Index des Maximums im Array A
Best-Case: O(n), Worst Case: O(n), Average Case: O(n)
Der Algorithmus sucht nach dem höchsten Index des Maximums im Array A mit den Zahlen 1, 6, 3, 6 und 4, indem das Maximum 6 mehrfach vorkommt. Man initialisiert den Suchwert x mit 0 und und durchläuft die Suche umgekehrt von hinten (A [(length – 1)]) nach vorne.
Initialisierung
Suchbereich A [1, 6, 3, 6, 4] mit fünf Elementen (n = 5)
Suchwert x = 0
aktuelles Maximum A[x] = A[0] = 1
erster Schritt
Suchbereich A [1, 6, 3, 6, 4]
Eingabe A[i] = A[ (length -1)] = A[(5-1)] = A[4] = 4
Vergleich A[i] > A[x] , 4 > 1, true
neues Maximum A[4] = 4
zweiter Schritt
Suchbereich A [1, 6, 3, 6, 4]
Eingabe A[i] = A[3] = 6
Vergleich A[i] > A[x] , 6 > 4, true
neues Maximum A[x] = A[3] = 6
dritter Schritt
Suchbereich A [1, 6, 3, 6, 4]
Eingabe A[i] = A[2] = 3
Vergleich A[i] > A[x] , 3 > 6, false
vierter Schritt
Suchbereich A [1, 6, 3, 6, 4]
Eingabe A[i] = A[1] = 6
Vergleich A[i] > A[x] , 6 = 6, false
fünfter Schritt
Suchbereich A [1, 6, 3, 6, 4]
Eingabe A[i] = A[0] = 1
Vergleich A[i] > A[x] , 1 > 6, false
Der Algorithmus terminiert am Ende der Liste nach den fünften Schritt bei der Eingabe von A[0] und gibt das Ergebnis 3 aus, da dies der größte Index ist, an dem das Maximum gefunden wurde ( A[3] = 6). Da er das gesamte Array durchlaufen muss, benötigt er n = 5 Vergleiche.
*** Pseudocode Finde größten Indexwert des Maximums *** input: A [1,6,3,6,4] def x = 0 For A.length-1 to 0 do if A[i] > A[x] then x = i End For return x
Beispiel 4:
Lineare Suche nach allen Indizes des Maximums im Array A
Best-Case: O(n), Worst Case: O(n), Average Case: O(n)
Der Algorithmus sucht nach allen Indizes des Maximums im Array A mit den Zahlen 1, 6, 3, 6 und 4. Dafür setzt man den Suchwert x auf 0 und definiert ein leeres Array indices, um die entsprechenden Indizes zu sammeln. Der Algorithmus speichert den ersten Index [0] und durchläuft das Array. Falls ein größerer x-Wert gefunden wird, wird x aktualisiert in indices ersetzt. Falls ein Wert gleich x ist, wird sein Index zum Array indices hinzugefügt.
Initialisierung
Suchbereich A [1, 6, 3, 6, 4] mit fünf Elementen (n = 5)
indices [ ]
Suchwert x = 0
Maximum A[x] = A[0] = 1
erster Schritt
Suchbereich A [1, 6, 3, 6, 4]
Eingabe A[i] = A[0] = 1
Vergleich A[i] > x, 1 = 1, append
indices [0]
zweiter Schritt
Suchbereich A [1, 6, 3, 6, 4]
Eingabe A[i] = A[1] = 6
Vergleich A[i] > x, 6 > 1, true
neues Maximum A[x] = A[1] = 6
indices [1]
dritter Schritt
Suchbereich A [1, 6, 3, 6, 4]
Eingabe A[i] = A[2] = 3
Vergleich A[i] > x, 3 > 6, false
indices [1]
vierter Schritt
Suchbereich A [1, 6, 3, 6, 4]
Eingabe A[i] = A[3] = 6
Vergleich A[i] > x, 6 = 6, append
indices [1,3]
fünfter Schritt
Suchbereich A [1, 6, 3, 6, 4]
Eingabe A[ i ] = A[4] = 4
Vergleich A[ i ] > x, 4 < 6, false
indices [1,3]
Der Algorithmus terminiert nach fünf Vergleichen bei A[4] und und gibt die Indizes [1, 3] als Positionen des größten Wertes zurück. Da er das gesamte Array durchlaufen muss, benötigt er n Vergleiche.
*** Pseudocode Finde alle Indices des Maximums ***
input: A [1,6,3,6,4]
def x = A[0]
def Indices[]
For A.length-1 to 0 do
if A[i] > x then
x = A[i]
indices = [i]
else if A[i] = x then
indices.append(i)
End For
return indices
Die Kommentarfunktion ist deaktiviert, aber Trackbacks und Dingbacks sind offen.