Lineare Suche - LinkFang.de





Lineare Suche


Lineare Suche ist ein Algorithmus, der auch unter dem Namen sequentielle Suche bekannt ist. Er ist 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 kann nur bei geordneten Listen benutzt werden.

Für ungeordnete Listen existiert mit Lazy Select noch ein randomisierter 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 der Komplexitätsklasse O(n), da sie im schlechtesten Fall (wenn der gesuchte Wert nicht gefunden werden kann) n Vergleiche benötigt.

Wenn die Daten zufallsverteilt sind, dann werden im Schnitt (n+1)/2 Vergleichsoperationen 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 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 gibt den Wert -1 zurück, wenn das gesuchte Element nicht im Array daten vorhanden ist. Ansonsten gibt es die Position des 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 alle Suchschlüssel in 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 des Suchschlüssels in 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) 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
*/
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


Kategorien: Suchalgorithmus

Quelle: Wikipedia - http://de.wikipedia.org/wiki/Lineare Suche (Vollständige Liste der Autoren des Textes [Versionsgeschichte])    Lizenz: CC-by-sa-3.0

Änderungen: Alle Bilder mit den meisten Bildunterschriften wurden entfernt. Ebenso alle zu nicht-existierenden Artikeln/Kategorien gehenden internen Wikipedia-Links (Bsp. Portal-Links, Redlinks, Bearbeiten-Links). Entfernung von Navigationsframes, Geo & Normdaten, Mediadateien, gesprochene Versionen, z.T. ID&Class-Namen, Style von Div-Containern, Metadaten, Vorlagen, wie lesenwerte Artikel. Ansonsten sind keine Inhaltsänderungen vorgenommen worden. Weiterhin kann es durch die maschinelle Bearbeitung des Inhalts zu Fehlern gerade in der Darstellung kommen. Darum würden wir jeden Besucher unserer Seite darum bitten uns diese Fehler über den Support mittels einer Nachricht mit Link zu melden. Vielen Dank!

Stand der Informationen: August 201& - Wichtiger Hinweis: Da die Inhalte maschinell von Wikipedia übernommen wurden, ist eine manuelle Überprüfung nicht möglich. Somit garantiert LinkFang.de nicht die Richtigkeit und Aktualität der übernommenen Inhalte. Sollten die Informationen mittlerweile fehlerhaft sein, bitten wir Sie darum uns per Support oder E-Mail zu kontaktieren. Wir werden uns dann innerhalb von spätestens 10 Tagen um Ihr Anliegen kümmern. Auch ohne Anliegen erfolgt mindestens alle drei Monate ein Update der gesamten Inhalte.