Lineare Suche
Zuletzt aktualisiert
Die lineare Suche (auch sequentielle Suche genannt) ist der einfachste Suchalgorithmus: Beginne beim ersten Element und vergleiche jedes mit dem Ziel, bis du einen Treffer findest oder keine Elemente mehr übrig sind. Sie macht keinerlei Annahmen über die Daten — das Array kann unsortiert sein, und die Elemente können alles sein, was sich auf Gleichheit vergleichen lässt.
Die Animation oben hebt jeden Vergleich hervor, während der Durchlauf von links nach rechts fortschreitet, und stoppt in dem Moment, in dem das Ziel erscheint. Ihre Einfachheit kostet Geschwindigkeit: Im schlechtesten Fall wird jedes Element geprüft, sie läuft also in O(n). Sind die Daten sortiert, findet die binäre Suche dieselbe Antwort in O(log n) — und wenn du zuerst sortierte Daten brauchst, sieh dir Merge Sort an.
Zeit- und Platzkomplexität
| Fall | Komplexität | Anmerkungen |
|---|---|---|
| Bester Fall | O(1) | Das erste Element ist das Ziel. |
| Durchschnittlicher Fall | O(n) | Im Schnitt wird die Hälfte der Elemente geprüft, bevor ein Treffer kommt. |
| Schlechtester Fall | O(n) | Das Ziel ist das letzte Element — oder gar nicht vorhanden. |
| Platz | O(1) | Nur der aktuelle Index wird gehalten. |
Schritt für Schritt
| Schritt | Was passiert |
|---|---|
| 1 | Beginne bei Index 0, dem ersten Element des Arrays. |
| 2 | Vergleiche das aktuelle Element mit dem Zielwert. |
| 3 | Sind sie gleich, gib den aktuellen Index zurück — gefunden. |
| 4 | Andernfalls gehe eine Position nach rechts und wiederhole. |
| 5 | Wird das Ende des Arrays ohne Treffer erreicht, ist das Ziel nicht vorhanden (gib -1 zurück). |
Durchgerechnetes Beispiel
Suche nach 5 in [7, 3, 9, 1, 5, 8, 2]:
| Vergleich | Index | Element | Ergebnis |
|---|---|---|---|
| 1 | 0 | 7 | 7 ≠ 5 — weiter suchen. |
| 2 | 1 | 3 | 3 ≠ 5 — weiter suchen. |
| 3 | 2 | 9 | 9 ≠ 5 — weiter suchen. |
| 4 | 3 | 1 | 1 ≠ 5 — weiter suchen. |
| 5 | 4 | 5 | 5 = 5 — bei Index 4 gefunden. |
Wann die lineare Suche verwenden
| Verwenden, wenn | Vermeiden, wenn |
|---|---|
| Die Daten unsortiert sind oder sich ständig ändern | Die Daten sortiert sind — die binäre Suche ist exponentiell schneller |
| Die Sammlung klein ist, sodass Einfachheit gewinnt | Der Datensatz groß ist und wiederholt durchsucht wird |
| Du nur sequenziellen Zugriff hast (Streams, verkettete Listen) | Du dir einen Index oder eine Hashtabelle für O(1)-Lookups leisten kannst |
Linear Search-Code
Eine saubere, lauffähige Linear Search-Implementierung in Python, JavaScript, Java, C++, C, Pseudocode. Wähle eine Sprache, kopiere den Code oder öffne ihn vorgeladen im Coddy-Playground.
Linear Search-Code in Python
Python
1def linear_search(a, target):2 # Scan left to right until the target appears3 for i in range(len(a)):4 if a[i] == target:5 return i6 return -17
8
9nums = [7, 3, 9, 1, 5, 8, 2]10print("Index of 5:", linear_search(nums, 5))11print("Index of 4:", linear_search(nums, 4))Linear Search-Code in JavaScript
JavaScript
1function linearSearch(a, target) {2 // Scan left to right until the target appears3 for (let i = 0; i < a.length; i++) {4 if (a[i] === target) return i;5 }6 return -1;7}8
9const nums = [7, 3, 9, 1, 5, 8, 2];10console.log("Index of 5:", linearSearch(nums, 5));11console.log("Index of 4:", linearSearch(nums, 4));Linear Search-Code in Java
Java
1public class Main {2 static int linearSearch(int[] a, int target) {3 // Scan left to right until the target appears4 for (int i = 0; i < a.length; i++) {5 if (a[i] == target) return i;6 }7 return -1;8 }9
10 public static void main(String[] args) {11 int[] nums = {7, 3, 9, 1, 5, 8, 2};12 System.out.println("Index of 5: " + linearSearch(nums, 5));13 System.out.println("Index of 4: " + linearSearch(nums, 4));14 }15}Linear Search-Code in C++
C++
1#include <iostream>2#include <vector>3
4int linearSearch(const std::vector<int>& a, int target) {5 // Scan left to right until the target appears6 for (std::size_t i = 0; i < a.size(); i++) {7 if (a[i] == target) return static_cast<int>(i);8 }9 return -1;10}11
12int main() {13 std::vector<int> nums = {7, 3, 9, 1, 5, 8, 2};14 std::cout << "Index of 5: " << linearSearch(nums, 5) << "\n";15 std::cout << "Index of 4: " << linearSearch(nums, 4) << "\n";16 return 0;17}Linear Search-Code in C
C
1#include <stdio.h>2
3int linear_search(const int a[], int n, int target) {4 /* Scan left to right until the target appears */5 for (int i = 0; i < n; i++) {6 if (a[i] == target) return i;7 }8 return -1;9}10
11int main(void) {12 int nums[] = {7, 3, 9, 1, 5, 8, 2};13 int n = sizeof(nums) / sizeof(nums[0]);14 printf("Index of 5: %d\n", linear_search(nums, n, 5));15 printf("Index of 4: %d\n", linear_search(nums, n, 4));16 return 0;17}Linear Search-Code in Pseudocode
Pseudocode
1DECLARE nums : ARRAY[1:7] OF INTEGER2DECLARE n : INTEGER3n ← 74nums[1] ← 75nums[2] ← 36nums[3] ← 97nums[4] ← 18nums[5] ← 59nums[6] ← 810nums[7] ← 211
12FUNCTION linearSearch(target : INTEGER) RETURNS INTEGER13 DECLARE i : INTEGER14 // Scan left to right until the target appears15 FOR i ← 1 TO n16 IF nums[i] = target THEN17 RETURN i18 ENDIF19 NEXT i20 RETURN -121ENDFUNCTION22
23OUTPUT "Index of 5 is ", linearSearch(5)24OUTPUT "Index of 4 is ", linearSearch(4)FAQ zur linearen Suche
Was ist die Zeitkomplexität der linearen Suche?
O(n) im durchschnittlichen und im schlechtesten Fall — der Durchlauf muss unter Umständen jedes Element besuchen — und O(1) im besten Fall, wenn das erste Element das Ziel ist. Sie benötigt O(1) zusätzlichen Platz.Braucht die lineare Suche sortierte Daten?
Nein — das ist ihr größter Vorteil. Die lineare Suche funktioniert auf völlig unsortierten Daten, weil sie jedes Element auf Gleichheit prüft; die Reihenfolge spielt nie eine Rolle. Die binäre Suche dagegen funktioniert nur auf sortierten Arrays.
Wann ist die lineare Suche besser als die binäre Suche?
Wenn die Daten unsortiert sind und nur einmal durchsucht werden (vorheriges Sortieren würde
O(n log n) kosten), wenn die Sammlung winzig ist, oder wenn du nur sequenziellen Zugriff hast, etwa auf einen Stream oder eine verkettete Liste. Für wiederholte Lookups auf sortierten Arrays gewinnt die binäre Suche.Ist die lineare Suche dasselbe wie die sequentielle Suche?
Ja — die beiden Namen beschreiben denselben Algorithmus: die Elemente der Reihe nach durchgehen, bis das Ziel gefunden ist oder die Sammlung endet.
Wie viele Vergleiche macht die lineare Suche im Durchschnitt?
Ist das Ziel vorhanden und mit gleicher Wahrscheinlichkeit an jeder Position, im Schnitt etwa
n/2 Vergleiche; fehlt das Ziel, genau n. Dieses lineare Wachstum ist der Grund für den Namen lineare Suche.Verwandte Ressourcen
Mehr Visualisierungen
