Lineare Suche
Kurz gesagt: Die lineare Suche prüft die Elemente nacheinander, bis sie das gesuchte findet oder am Ende ankommt: O(n) Vergleiche, und sie funktioniert auch mit einer unsortierten Liste.
Problem
Der Scanner im Lager
Im Lager stehen die Produkte in einer Liste, in der Reihenfolge, in der sie angekommen sind: das Mehl vom Montag, der Zucker vom Dienstag, das Öl, der Reis. Ein Mitarbeiter scannt eine Kiste, und das Programm muss das Produkt anhand seines Barcodes finden:
const shelf = [ { barcode: "3800200101112", name: "Mehl" }, { barcode: "3800200104403", name: "Zucker" }, { barcode: "3800200107251", name: "Öl" }, { barcode: "3800200102690", name: "Reis" }, { barcode: "3800200109958", name: "Salz" }, { barcode: "3800200105837", name: "Kaffee" },];Die Barcodes sind nicht sortiert. Du kannst die Liste nicht in der Mitte aufschlagen und sagen „der Reis ist weiter hinten“: Der nächste Barcode kann alles sein. Wie findest du das Produkt, und was kostet es bei 50.000 Produkten und 2000 Scans am Tag?
Die Idee
Du schaust in jede Kiste
Da die Reihenfolge nicht hilft, bleibt nur eins: Du beginnst bei der ersten Kiste und vergleichst ihren Barcode mit dem gesuchten. Passt er, bist du fertig: Du gibst den Platz zurück. Wenn nicht, gehst du zur nächsten. Wenn die Kisten zu Ende sind, ist das Produkt nicht da.
Das ist die lineare Suche: Du gehst die Elemente nacheinander durch, bis du das gesuchte findest oder am Ende ankommst. Sie liefert den Platz (den Index) oder ein Zeichen für „nicht da“: -1, weil es keinen Platz -1 gibt.
Sieh es dir an
Der Zeiger am Regal
function find(shelf, barcode) { for (let i = 0; i < shelf.length; i++) { if (shelf[i].barcode === barcode) { return i; } } return -1;}const rice = find(shelf, "3800200102690");console.log("3800200102690 ->", rice, shelf[rice].name);console.log("3800200100000 ->", find(shelf, "3800200100000"));3800200102690 -> 3 Reis3800200100000 -> -1function find(shelf, barcode) { for (let i = 0; i < shelf.length; i++) { if (shelf[i].barcode === barcode) { return i; } } return -1;}
const rice = find(shelf, "3800200102690");const missing = find(shelf, "3800200100000");Schritt für Schritt, in Worten
- Der Scanner liest den Barcode des Reises: 3800200102690. find beginnt bei der ersten Kiste.
- Er vergleicht den Barcode jeder Kiste mit dem gesuchten: mehl, zucker, öl. Kein Treffer.
- Die vierte Kiste ist der Reis. return 3: gefunden nach 4 Vergleichen.
- Ein Barcode, den das Lager nicht hat: 3800200100000. find beginnt wieder von vorn.
- Der Zeiger geht an jeder Kiste vorbei, und keine passt.
- Die Kisten sind zu Ende: return -1 nach 6 Vergleichen. Ein fehlendes Produkt ist der schlechteste Fall: n Vergleiche bei n Kisten.
Der Reis wird nach 4 Vergleichen gefunden. Der fehlende Barcode geht durch alle 6 Kisten: Nur so lässt sich sagen, dass er nicht da ist.
Probier es aus
Ergänze
Was gibt find zurück, wenn die Kisten zu Ende sind?
function find(shelf, barcode) {
for (let i = 0; i < shelf.length; i++) {
if (shelf[i].barcode === barcode) {
return i;
}
}
return ;
}-1 ist kein Platz in der Liste, also kann man es nicht mit einem gefundenen Produkt verwechseln. Wer find aufruft, prüft auf -1, bevor er das Ergebnis benutzt.Die Idee
Wie viele Vergleiche
Die Zahl der Vergleiche hängt davon ab, wo das Produkt liegt:
- der beste Fall: die erste Kiste, 1 Vergleich;
- der schlechteste Fall: die letzte Kiste oder ein Produkt, das nicht da ist, n Vergleiche;
- der typische Fall: Wenn jeder Platz gleich wahrscheinlich ist, im Durchschnitt etwa n/2.
Der schlechteste und der typische Fall wachsen mit n, deshalb ist die lineare Suche O(n). Das Programm zählt mit:
function comparisons(shelf, barcode) { let count = 0; for (const product of shelf) { count++; if (product.barcode === barcode) { return count; } } return count;}console.log("Mehl:", comparisons(shelf, "3800200101112"));console.log("Reis:", comparisons(shelf, "3800200102690"));console.log("Fehlt:", comparisons(shelf, "3800200100000"));Mehl: 1Reis: 4Fehlt: 6Lass die beiden Extremfälle in einem großen Lager laufen. Wir zählen einen Vergleich pro Kiste:
- Der Barcode fehlt (schlechtester Fall)
O(n) - Das erste Produkt (bester Fall)
O(1)
| Algorithmus | n = 10 | n = 1.000 | n = 100.000 |
|---|---|---|---|
| Der Barcode fehlt (schlechtester Fall) | 10 | 1.000 | 100.000 |
| Das erste Produkt (bester Fall) | 1 | 1 | 1 |
Die erste Kiste kostet bei jedem n 1 Vergleich: O(1). Ein fehlendes Produkt kostet n: Bei 100.000 Produkten sind das 100.000 Vergleiche. Der Speicher ist O(1): ein Index.
Probier es aus
Sage die Ausgabe voraus
Das Salz ist die fünfte Kiste im Regal. Wie viele Vergleiche macht die Suche?
function comparisons(shelf, barcode) { let count = 0; for (const product of shelf) { count++; if (product.barcode === barcode) { return count; } } return count;}
console.log("Salz:", comparisons(shelf, "3800200109958"));Sieh es dir an
Die eingebauten Funktionen suchen genauso
Jede Sprache hat eine fertige Suche in einer Liste. Darin steckt dieselbe Schleife:
const barcodes = [ "3800200101112", "3800200104403", "3800200107251", "3800200102690", "3800200109958", "3800200105837",];console.log(barcodes.indexOf("3800200102690"));console.log(barcodes.indexOf("3800200100000"));console.log(barcodes.includes("3800200102690"));console.log(shelf.findIndex((p) => p.barcode === "3800200102690"));3-1true3indexOf liefert den Platz oder -1, includes nur true oder false, und findIndex sucht nach einer Regel, die als Funktion übergeben wird. Alle gehen ab dem ersten Element vor: O(n).Ein Aufruf sieht nach einer Operation aus, aber darin stecken bis zu n Vergleiche. Die eingebaute Funktion ist um einen konstanten Faktor schneller als deine Schleife, nicht um eine Größenordnung.
Probier es aus
Finde den Fehler
Ein Kollege hat die Suche so geschrieben. Das Mehl wird gefunden, und der Reis „ist nicht da“:
function find(shelf, barcode) { for (let i = 0; i < shelf.length; i++) { if (shelf[i].barcode === barcode) { return i; } else { return -1; } } return -1;}console.log(find(shelf, "3800200101112"));console.log(find(shelf, "3800200102690"));0-1In welcher Zeile steckt der Fehler?
Wähle die Zeile mit dem Fehler.
Ein else mit return in der Schleife liefert „nicht da“ gleich nach der ersten Kiste, die nicht passt. Die Schleife kommt nie zur zweiten. Der Test mit dem Mehl besteht, weil es als Erstes liegt. „Nicht da“ darf man erst sagen, wenn die Kisten zu Ende sind: Entferne das else und lass das einzige „nicht da“ nach der Schleife.
Die Idee
Wann sie passt und wann nicht
Die lineare Suche ist die richtige Wahl, wenn:
- es wenige Produkte gibt: Zehn oder hundert Vergleiche merkt man nicht;
- du einmal suchst: Jeder schnellere Weg braucht erst mindestens n Schritte Vorbereitung;
- die Daten unsortiert sind oder sich ständig ändern und es nichts zu pflegen gibt.
Sie passt nicht bei vielen Suchen. 2000 Scans am Tag in 50.000 Produkten sind bis zu 100.000.000 Vergleiche. Dann bereitest du die Daten einmal vor:
- eine Tabelle Barcode → Produkt (
Map): einmal 50.000 Schritte, danach ist jede Suche im Durchschnitt O(1); - eine sortierte Liste und die binäre Suche: Das Sortieren ist einmal O(n log n), und jede Suche danach ist O(log n), bei 50.000 etwa 16 Vergleiche.
const byBarcode = new Map();for (const product of shelf) { byBarcode.set(product.barcode, product);}console.log(byBarcode.get("3800200102690").name);console.log(byBarcode.get("3800200100000"));ReisundefinedDie Tabelle kostet Speicher: noch einmal n Plätze. Das ist derselbe Tausch von Zeit gegen Speicher wie beim Set in der Lektion „Speicherkomplexität“.
Übung
Alle Kisten eines Produkts
Löse die Aufgabe in deinem Editor.
Inventur. Ein Produkt kann mit mehreren Lieferungen gekommen sein und an mehreren Plätzen in der Liste stehen. Schreibe findAll(shelf, barcode), das alle Plätze des Barcodes zurückgibt, nicht nur den ersten. Das Regal ist wie oben, dazu mehr Reis und mehr Salz am Ende (Plätze 6 und 7).
Reis: 3, 6Salz: 4, 7Weitere Aufgaben
- Der letzte Platz. Gib den letzten Platz des Barcodes zurück. Wo fängt man besser an?
- Nach Name, ohne Groß- und Kleinschreibung. Finde das Produkt nach Namen („reis“ und „Reis“ sind dasselbe). Wie viele Vergleiche sind es im schlechtesten Fall?
- Produkte unter dem Mindestbestand. Liste alle Produkte mit weniger als 10 Stück auf Lager auf. Kannst du vor dem Ende aufhören?
Test