Lineare und binäre Suche live nebeneinander. Bei welchem n lohnt sich der Aufwand des Sortierens? Wann ist Linear schneller? Klausur-Übersicht.
Lineare Suche und Binäre Suche unterscheiden sich vor allem in einer Voraussetzung: Binäre Suche braucht ein sortiertes Array, Lineare Suche nicht. Daraus ergeben sich unterschiedliche Komplexitäten und Anwendungsfälle.
Die Kernunterschiede:
In Klausuren wirst du oft gefragt: bei welcher Datenmenge n und welcher Anzahl Suchen lohnt sich Sortieren plus Binäre Suche statt Lineare Suche?. Faustregel: wenn du m-mal in n Elementen suchst, ist Binär lohnenswert sobald m * log(n) < n.
| Algorithmus | Worst Case | Average Case | Best Case | Voraussetzung |
|---|---|---|---|---|
| Lineare Suche | O(n) | O(n) | O(1) | Keine |
| Binäre Suche | O(log n) | O(log n) | O(1) | Sortiert |
| n | Linear | Binär | Faktor |
|---|---|---|---|
| 100 | 100 | 7 | 14× |
| 1.000 | 1.000 | 10 | 100× |
| 1.000.000 | 1.000.000 | 20 | 50.000× |
| 1 Milliarde | 1 Mrd. | 30 | 33 Mio× |
Bei großen Daten ist Binär ungeschlagen.
Arrays.binarySearch() und Collections.binarySearch()bisect Modul (bisect_left, bisect_right)std::binary_search und std::lower_boundAber im Kopf haben muss man beide, sie tauchen in jeder Algorithmik-Klausur auf.
Weiter im Tab "Interaktiv" siehst du beide Algorithmen live nebeneinander.
Alle Tabs der Lerneinheit (Übersicht · Interaktiv · Quiz) als durchgehender Text. Ideal zum Wiederholen vor der Klausur — und für Suchmaschinen wie Google, Bing und KI-Suche (ChatGPT, Perplexity).
Lineare Suche und Binäre Suche unterscheiden sich vor allem in einer Voraussetzung: Binäre Suche braucht ein sortiertes Array, Lineare Suche nicht. Daraus ergeben sich unterschiedliche Komplexitäten und Anwendungsfälle.
Wie wächst der Aufwand eines Algorithmus mit der Eingabe-Größe? Konstant, linear, quadratisch, und wann macht der Unterschied wirklich was aus?
Der intuitive Sortieralgorithmus: zwei verschachtelte Schleifen, größere Werte blubbern nach oben. Einfach zu erklären, in der Praxis aber zu langsam: O(n²).
Teile und Herrsche. Garantierte O(n log n) durch rekursives Halbieren plus Merge. Stabil, aber braucht O(n) Zusatzspeicher. Klausur-Klassiker schlechthin.
Die Kernunterschiede:
In Klausuren wirst du oft gefragt: bei welcher Datenmenge n und welcher Anzahl Suchen lohnt sich Sortieren plus Binäre Suche statt Lineare Suche?. Faustregel: wenn du m-mal in n Elementen suchst, ist Binär lohnenswert sobald m * log(n) < n.
| Algorithmus | Worst Case | Average Case | Best Case | Voraussetzung |
|---|---|---|---|---|
| Lineare Suche | O(n) | O(n) | O(1) | Keine |
| Binäre Suche | O(log n) | O(log n) | O(1) | Sortiert |
| n | Linear | Binär | Faktor |
|---|---|---|---|
| 100 | 100 | 7 | 14× |
| 1.000 | 1.000 | 10 | 100× |
| 1.000.000 | 1.000.000 | 20 | 50.000× |
| 1 Milliarde | 1 Mrd. | 30 | 33 Mio× |
Bei großen Daten ist Binär ungeschlagen.
Arrays.binarySearch() und Collections.binarySearch()bisect Modul (bisect_left, bisect_right)std::binary_search und std::lower_boundAber im Kopf haben muss man beide, sie tauchen in jeder Algorithmik-Klausur auf.
Weiter im Tab "Interaktiv" siehst du beide Algorithmen live nebeneinander.
Wähle eine Array-Größe und ein Target. Beide Algorithmen suchen auf dem gleichen sortierten Array parallel. Der Operation-Counter zählt Vergleiche mit.
Probier folgendes:
Interaktive Visualisierung
Vergleicht lineare und binäre Suche mit Schritt-Counter pro Algorithmus.
Die Animation lügt nicht. Linear marschiert stur von links nach rechts, Binär springt zielsicher zum Mittelpunkt und halbiert. Bei großen n ist Binär praktisch sofort fertig, während Linear noch lange weiterläuft.
Der Operation-Zähler bestätigt was die Big-O-Analyse vorhersagt: n wächst linear, log₂ n fast nicht.
Klausurfragen mit Lösungen (6)
Antwort: Nur Lineare Suche
Erklärung: Lineare Suche funktioniert auf jedem Array, sortiert oder nicht. Binäre Suche braucht zwingend ein sortiertes Array, sonst kann sie nicht entscheiden, ob das Target links oder rechts vom Pivot liegt.
Antwort: Etwa 1.000 mehr
Erklärung: Linear: 1024 Vergleiche im Worst Case. Binär: log₂(1024) = 10. Differenz: ~1.014 Vergleiche, also etwa 1.000 mehr.
Antwort: Linear suchen: O(n)
Erklärung: Bei einer einzigen Suche ist Linear schneller. Sortieren kostet O(n log n) ≈ 10.000 Operationen, Linear nur O(n) = 1.000 Operationen. Der Sortier-Aufwand lohnt sich erst, wenn du viele Suchen auf demselben Array machst.
Antwort: Beide gleich (jeweils 1 Vergleich)
Erklärung: Best Case ist bei beiden O(1): Linear findet das Element direkt am Anfang, Binär findet es genau im ersten Mittelpunkt. Im Average und Worst Case sind die Verfahren aber dramatisch unterschiedlich.
Antwort: Das Array muss sortiert sein
Erklärung: Binäre Suche braucht ein sortiertes Array, sonst funktioniert das Halbierungs-Prinzip nicht. Lineare Suche hat diese Voraussetzung nicht und funktioniert auf jedem Array.
Antwort: Binäre Suche
Erklärung: Binäre Suche skaliert logarithmisch (O(log n)). Bei 1 Milliarde Einträgen reichen 30 Vergleiche, bei 1 Billion nur 40. Lineare Suche bräuchte entsprechend 1 Mrd. bzw. 1 Bio. Vergleiche.