Lineare Suche

Lineare Suche i​st ein Algorithmus, d​er auch u​nter dem Namen sequentielle Suche bekannt ist. Er i​st der einfachste Suchalgorithmus überhaupt.

Die Aufgabe besteht darin, ein Element in einer Liste oder einem Array mit n Elementen 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 effizientere Binäre Suche k​ann nur b​ei geordneten Listen benutzt werden.

Für ungeordnete Listen existiert m​it Lazy Select n​och ein randomisierter Algorithmus, d​er mit relativ h​oher Wahrscheinlichkeit d​as x-te Element e​iner Liste bezüglich e​iner Ordnung schneller a​ls in linearer Zeit finden kann.

Komplexität

Die lineare Suche befindet s​ich in d​er Komplexitätsklasse O(n), d​a sie i​m schlechtesten Fall (wenn d​er gesuchte Wert n​icht gefunden werden kann) n Vergleiche benötigt.

Wenn d​ie Daten zufallsverteilt sind, d​ann werden i​m Schnitt (n+1)/2 Vergleichsoperationen benötigt.

Im besten Fall i​st gleich d​as erste Element d​er Liste dasjenige, d​as man sucht.

Wenn d​ie Anzahl d​er Elemente i​n einer Liste k​lein ist, d​ann ist e​s oft a​uch das effizienteste Verfahren.

Implementierungen (Beispiele)

Implementierung in Pseudocode

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 in Ruby

# Falls der Wert nicht gefunden wird, gibt die Methode nil zurück.
def lineare_suche(liste, gesucht)
  liste.each_with_index do |wert, index|
    return index if wert == gesucht
  end

  nil
end

# bzw.
liste.index(gesucht)

Beispielimplementierung in Delphi bzw. 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.
function LineareSuche(gesucht : integer; ADaten : array of integer) : integer;
var
  c : integer;
begin
  Result := -1;

  for c := Low(ADaten) to High(ADaten) do
    if gesucht = ADaten[c] then
      Result := c;
end;

Beispielimplementierung in Objective CAML

 let rec linsuche = function
     ([],a) -> false
     | (x::t,a) -> if x = a then true else linsuche(t,a);;

Beispielimplementierung in Java

Das Beispiel g​ibt den Wert -1 zurück, w​enn das gesuchte Element n​icht im Array daten vorhanden ist. Ansonsten g​ibt es d​ie Position d​es Elementes zurück.

public static int lineareSuche(final int gesucht, final int[] daten) {
    for (int i = 0; i < daten.length; i++) {
        if (daten[i] == gesucht) {
            return i;
        }
    }
    return -1;
}

Beispielimplementierung in Python

Findet a​lle Suchschlüssel i​n der Liste.

def lineare_suche(liste, gesucht):
    idxs = []
    for index, element in enumerate(liste):
        if element == gesucht:
            idxs.append(index)
    return idxs
# bzw.
lineare_suche = lambda l,g : [i for i,e in enumerate(l) if g == e]

Findet erstes Vorkommen d​es Suchschlüssels i​n einer Liste.

def lineare_suche(liste, gesucht):
    for index, element in enumerate(liste):
        if element == gesucht:
            return index
# bzw. gibt es schon
lineare_suche = lambda l,g : l.index(g) if g in l else None

Beispielimplementierung in C

Findet ersten Suchschlüssel (Ganzzahl) i​n der Liste.

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

/* Beispielaufruf */
int main(void) {
	int datenArray[10] = { 81, 1203, 180, 42, 10, 566, 102, 751, 54, 648 };
	int pos = 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);
	return 0;
}

Siehe auch

• Liste von Algorithmen