Algorithmusgratis

Lineare Suche

Prüfe die Elemente nacheinander, bis du das Ziel findest. Der einfachste O(n)-Algorithmus.

Zeit: O(n)
Speicher: O(1)

// Schritt für Schritt

Schritt 1 / 5

1function linearSearch(nums, target) {2  for (let i = 0; i < nums.length; i++) {3    if (nums[i] === target) return i;4  }5  return -1;6}

target: = 6
n: = 6
checks: = 1

nums[0] = 7 ist nicht 6. Bisherige Prüfungen: 1.

Tipp: Mit den Pfeiltasten durch die Schritte gehen.

So funktioniert es

Die lineare Suche schaut sich jedes Element der Reihe nach an. Liegt das Ziel weit vorne, geht es schnell, im schlechtesten Fall prüft sie aber alle n Elemente. Der Aufwand wächst also im Gleichschritt mit der Eingabe: doppelt so großes Array, doppelt so viele Prüfungen. Genau das bedeutet O(n). Achte beim Durchgehen auf den Zähler checks.