Lineare Suche

Lineare Sucheist einAlgorithmus,der auch unter dem Namensequentielle Suchebekannt ist. Er ist der einfachsteSuchalgorithmusüberhaupt.

Die Aufgabe besteht darin, ein Element in einer Liste oder einemArraymitnElementen zu finden. Man geht dazu die Liste Element für Element durch, bis man es gefunden hat. Der Suchaufwand wächst linear mit der Anzahl der Elemente in der Liste.

Die effizientereBinäre Suchekann nur bei geordneten Listen benutzt werden.

Für ungeordnete Listen existiert mitLazy Selectnoch einrandomisierter Algorithmus,der mit relativ hoher Wahrscheinlichkeit das x-te Element einer Liste bezüglich einer Ordnung schneller als in linearer Zeit finden kann.

Komplexität

Die lineare Suche befindet sich in derKomplexitätsklasseO(n),da sie im schlechtesten Fall (wenn der gesuchte Wert nicht gefunden werden kann)nVergleiche benötigt.

Wenn die Daten zufallsverteilt sind, dann werden imSchnitt(n+1)/2Vergleichsoperationen benötigt.

Im besten Fall ist gleich das erste Element der Liste dasjenige, das man sucht.

Wenn die Anzahl der Elemente in einer Liste klein ist, dann ist es oft auch das effizienteste Verfahren.

Implementierungen (Beispiele)

Implementierung inPseudocode

BEGINN LinearSearch

EINGABE: (S)uchschlüssel, (A)rray

VARIABLE: N = Anzahl Elemente im Array 'A'
VARIABLE: SucheErfolgreich = falsch
VARIABLE: i = 0

FÜR i BIS N ODER SucheErfolgreich
WENN A[i] = S
DANN SucheErfolgreich = wahr

WENN SucheErfolgreich = wahr
DANN AUSGABE: i
SONST AUSGABE: Suche nicht erfolgreich

ENDE

Beispielimplementierung inRuby

# Falls der Wert nicht gefunden wird, gibt die Methode nil zurück.
deflineare_suche(liste,gesucht)
liste.each_with_indexdo|wert,index|
returnindexifwert==gesucht
end

nil
end

# bzw.
liste.index(gesucht)

Beispielimplementierung inDelphibzw.Free Pascal

// Durchsucht ein Array of Integer nach einem gesuchten Integer-Wert.
// Wird der gesuchte Wert gefunden, gibt die Funktion den Index des Wertes zurück.
// Falls der Wert nicht gefunden wird, gibt die Funktion -1 zurück.
functionLineareSuche(gesucht:integer;ADaten:arrayofinteger):integer;
var
c:integer;
begin
Result:=-1;

forc:=Low(ADaten)toHigh(ADaten)do
ifgesucht=ADaten[c]then
Result:=c;
end;

Beispielimplementierung inObjective CAML

letreclinsuche=function
([],a)->false
|(x::t,a)->ifx=athentrueelselinsuche(t,a);;

Beispielimplementierung inJava

Das Beispiel gibt den Wert-1zurück, wenn das gesuchte Element nicht im Arraydatenvorhanden ist. Ansonsten gibt es die Position des Elementes zurück.

publicstaticintlineareSuche(finalintgesucht,finalint[]daten){
for(inti=0;i<daten.length;i++){
if(daten[i]==gesucht){
returni;
}
}
return-1;
}

Beispielimplementierung inPython

Findet alle Suchschlüssel in der Liste.

deflineare_suche(liste,gesucht):
idxs=[]
forindex,elementinenumerate(liste):
ifelement==gesucht:
idxs.append(index)
returnidxs
# bzw.
lineare_suche=lambdal,g:[ifori,einenumerate(l)ifg==e]

Findet erstes Vorkommen des Suchschlüssels in einer Liste.

deflineare_suche(liste,gesucht):
forindex,elementinenumerate(liste):
ifelement==gesucht:
returnindex
# bzw. gibt es schon
lineare_suche=lambdal,g:l.index(g)ifginlelseNone

Beispielimplementierung inC

Findet ersten Suchschlüssel (Ganzzahl) in der Liste.

#include<stdio.h>
/*
int*daten = Zeiger auf zu durchsuchende Daten
int datenlaenge = Größe des zu durchsuchenden "Arrays"
int suche = Gesuchte Ganzzahl
*/
intsuche_sequenziell(int*daten,intdatenlaenge,intsuche){
inti;
for(i=0;i<datenlaenge;i++)
if(daten[i]==suche)
returni;
return-1;
}

/* Beispielaufruf */
intmain(void){
intdatenArray[10]={81,1203,180,42,10,566,102,751,54,648};
intpos=suche_sequenziell(datenArray,10,42);
/* -1 für nicht gefunden, ansonsten (erste) Position im Array, mit 0 beginnend */
if(pos<0)
printf("Nicht gefunden");
else
printf("Gefunden an Position %d",pos);
return0;
}

Siehe auch

• Liste von Algorithmen