Lineare vs. binäre Suche
Lineare vs. binäre Suche ist ein interaktives Experiment in Algorithmen sichtbar gemacht, einer kostenlosen Simulation aus dem StudyFi Lab, die direkt im Browser läuft.
Die lineare Suche prüft die Elemente eins nach dem anderen und braucht im schlechtesten Fall n Schritte — O(n). Die binäre Suche funktioniert nur auf einem sortierten Array: Sie schaut in die Mitte und verwirft je nach Ergebnis eine ganze Hälfte. Nach jedem Schritt bleibt höchstens die Hälfte übrig, daher genügen höchstens ⌈log₂(n+1)⌉ Schritte — O(log n). Bei 40 Elementen sind das 6 Schritte statt 40.
Probier das: Stelle 40 Elemente ein und suche den letzten Wert. Wähle dann eine Zahl, die nicht im Array steht — wie viele Schritte braucht jede Suche, um das festzustellen?
Häufige Fragen
Was zeigt das Experiment „Lineare vs. binäre Suche“?
Die lineare Suche prüft die Elemente eins nach dem anderen und braucht im schlechtesten Fall n Schritte — O(n). Die binäre Suche funktioniert nur auf einem sortierten Array: Sie schaut in die Mitte und verwirft je nach Ergebnis eine ganze Hälfte. Nach jedem Schritt bleibt höchstens die Hälfte übrig, daher genügen höchstens ⌈log₂(n+1)⌉ Schritte — O(log n). Bei 40 Elementen sind das 6 Schritte statt 40.
Wie probiere ich „Lineare vs. binäre Suche“ aus?
Stelle 40 Elemente ein und suche den letzten Wert. Wähle dann eine Zahl, die nicht im Array steht — wie viele Schritte braucht jede Suche, um das festzustellen?
Lernst du für eine Prüfung?
Lade deine Notizen hoch und StudyFi macht daraus Karteikarten, Tests und Podcasts.