Benutzer:Borstel/bla

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.

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 für einen Array

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 den Array in dem die Zahlen stehen. Der dritte Parameter "length" steht für die Anzahl der Elemente im Array.

Rückgabewert

Der Integer steht für die Stelle im Array an dem die gesuchte Zahl das erste mal gefunden wird. Wenn die Suche erfolglos abgeschlossen wird, wird -1 zurück gegeben.

Implementierung für eine verkettete Liste

struct ListNode {
    int value;
    struct ListNode* prev;
};

struct ListNode* linearSearch(int key, struct ListNode* list) {
    // kommt...
}