Algorithmen und Datenstrukturen in C/ Lineare Suche

Die lineare Suche (oder auch sequentielle Suche) ist der einfachste Suchalgorithmus überhaupt. Es wird ein Element in einer Liste oder einem Array mit n Elementen gesucht. Dabei ist irrelevant, ob der Array bereits sortiert ist oder nicht.

Lineare Suche

Der Suchaufwand wächst linear mit der Anzahl der Elemente. Wenn die Daten zufallsverteilt sind, dann werden im Schnitt n/2 Vergleichsoperationen benötigt. Im besten Fall ist gleich das erste Element der Liste dasjenige, das man sucht, im schlechtesten ist es das letzte.

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

Implementierung

Die Suche in einer Liste von Integer-Werten wird wie folgt definiert:

int linearSearch(int key, int *array, int length) {
    int i;

    for (i = 0; i < length; i++)
        if (array[i] == key)
            return i;

    return -1;
}

Parameter

Die Funktion benötigt drei Parameter. Der erste Parameter "key" ist die Zahl, nach der gesucht wird. Der zweite Parameter ist ein Zeiger auf das Array, in dem die Elemente stehen. Der dritte Parameter "length" steht für die Anzahl der Elemente im Array.

Rückgabewert

Der Rückgabewert ist ein Integer. Dieser ist die Stelle im Array, an dem der gesuchte Wert das erste Mal gefunden wird. Wenn die Suche erfolglos abgeschlossen wird, wird -1 zurück gegeben.

Hoch zu Inhaltsverzeichnis