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 (O(n) vs O(logn)) und Anwendungsfälle. Du lernst hier die Break-even-Analyse: Binäre Suche selbst kostet O(logn); falls die Daten vorher sortiert werden müssen, kommt typischerweise O(nlogn) Sortieraufwand hinzu. Bei nur einer einzigen Suche lohnt sich das fast nie, bei vielen Suchen (m Suchen mit m ungefähr ≥logn) klar. Außerdem die Praxis-Faustregel wann lineare Suche schneller ist (bei sehr kleinen Arraysn<10–30, hardware-abhängig, weil Cache-Lokalität und geringere Konstanten-Faktoren die logn-Vorteile schlagen), und die typische Klausurfrage "wann nimmst du was?" mit der Antwort: Sortierungs-Voraussetzung prüfen, Anzahl der Suchen vs Sortier-Kosten abwägen.
Die Kernunterschiede:
Lineare Suche: O(n), keine Voraussetzung, prüft jedes Element der Reihe nach
Binäre Suche: O(log n), Array muss sortiert sein, halbiert den Suchraum bei jedem Schritt
Sortier-Aufwand: Binäre Suche selbst ist O(logn); falls die Daten vorher sortiert werden müssen, kommt typischerweise O(nlogn) Sortieraufwand hinzu. Lohnt sich nur bei mehrfachen Suchen
Praxis: bei kleinen oder einmal durchsuchten Datenmengen → Linear; bei großen sortierten Datenmengen oder häufigen Suchen → Binär
In Klausuren wirst du oft gefragt: bei welcher Datenmenge n und welcher Anzahl Suchen lohnt sich Sortieren plus Binäre Suche statt Lineare Suche?.
Break-even-Vergleich (m Suchen in n Elementen):
Wenn das Array bereits sortiert ist: Binäre Suche lohnt sich pro Suche fast immer bei großen n, vergleiche m⋅n (linear) mit m⋅logn (binär).
Wenn erst sortiert werden muss: vergleiche m⋅n (linear ohne Sortieren) mit nlogn+mlogn (Sortieren + m binäre Suchen). Sortieren plus binäre Suchen lohnt sich also, wenn nlogn+mlogn<m⋅n, also wenn m>n−lognnlogn, das ist für große n ungefähr m>logn. Das heißt:m lineare Suchen kosten m⋅n Vergleiche, m binäre Suchen nur m⋅logn Vergleiche, plus einmaliges Sortieren. Sind die Daten bereits sortiert oder werden sie dauerhaft sortiert gehalten, entfällt dieser einmalige Sortierblock komplett, dann lohnt sich Binäre Suche pro Lookup direkt.
Konkretes Beispiel (n=10000):
m (Anzahl Suchen)
Linear: m⋅n
Sortieren + Binär: nlogn+mlogn
Wer gewinnt?
m=1
10000
≈132877+13≈132890
Linear
m=10
100000
≈132877+130≈133007
Linear
m=100
1000000
≈132877+1330≈134207
Binär (Faktor ~7)
m=1000
10000000
≈132877+13300≈146177
Binär (Faktor ~68)
Break-even liegt hier ungefähr bei m≈14 Suchen, das ist nahe an log210000≈13. Bei m<14 ist eine einmalige lineare Suche pro Query billiger als der Sortier-Aufwand. Diese Rechnung ignoriert konstante Faktoren, in der Praxis verschiebt sich der Break-even leicht je nach Sortieralgorithmus, Hardware und Cache-Verhalten.
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
Größenordnung log2n vs n (Binär exakt: ⌈log2(n+1)⌉):
n
Linear (Worst)
Binär (~ log2n)
Faktor
100
100
~7
~14×
1.024
1.024
11
~93×
1.000.000
1.000.000
20
~50.000×
1 Mrd.
1 Mrd.
30
~33 Mio×
Bei großen sortierten Arrays ist Binäre Suche deutlich schneller als Lineare Suche. Für sehr viele exakte Lookups können Hash-Strukturen mit durchschnittlich O(1) noch besser sein, dafür ohne sortierte Traversierung oder Range-Abfragen.
Lineare Suche:
Bei sehr kleinen Arrays kann lineare Suche durch Cache-Lokalität und geringere Konstanten-Faktoren schneller sein. Die genaue Schwelle liegt typisch bei n<10–30, ist aber hardware-abhängig und gilt ohnehin nur in Mikro-Benchmarks; in Klausuren reicht "kleine Arrays"
Bei unsortierten Daten ohne Sortier-Möglichkeit
Bei einmaligen Suchen, wo der Sortier-Aufwand sich nicht lohnt
Binäre Suche:
Bei großen sortierten Arrays
Bei vielen wiederholten Suchen auf demselben Array
Bei Datenbank-Indizes, B-Bäume/B+-Bäume nutzen sortierte Schlüssel und logarithmische Baumstrukturen, das Prinzip ist ähnlich effizient wie binäre Suche, aber nicht einfach binäre Suche auf einem Array
Java: Arrays.binarySearch() und Collections.binarySearch() setzen sortierte Daten voraus, bei unsortierten Daten ist das Ergebnis undefiniert. Bei Duplikaten ist nicht garantiert, welcher passende Index zurückgegeben wird.
Python: bisect Modul liefert primär Einfügepositionen in sortierten Listen (bisect_left, bisect_right). Für Existenzprüfung danach: pos < len(a) and a[pos] == target.
C++: std::binary_search liefert nur bool. Für die Position des ersten passenden Elements: std::lower_bound.
Aber im Kopf haben muss man beide, sie tauchen in jeder Algorithmik-Klausur auf.
Auch wenn binäre Suche asymptotisch klar gewinnt, gibt es Szenarien wo lineare Suche pragmatisch die richtige Wahl ist. Bei sehr kleinen Arrays, oft im niedrigen zweistelligen Bereich, je nach Sprache, Hardware und Datenlayout, sind die Konstanten und die einfache CPU-Pipeline der linearen Suche oft schneller, weil binäre Suche eine Division/Vergleich/Sprung-Logik pro Schritt braucht. Bei unsortierten Daten ohne Sortier-Möglichkeit (z. B. Streaming-Daten, Log-Files) ist binäre Suche schlicht nicht anwendbar. Bei einer einmaligen Suche lohnt sich der Sortieraufwand O(nlogn) fast nie, da n Vergleiche linear ohnehin billiger sind als nlogn Sortier-Vergleiche.
Bei vielen Suchen auf demselben Datensatz (m Suchen, m groß) dreht sich das Verhältnis. Sortier-Kosten O(nlogn) amortisieren sich über die m Suchen, die danach jeweils O(logn) statt O(n) kosten. Daher die Break-even-Faustregel: ab ungefähr m>log2n Suchen wird das Vorsortieren günstiger als ein linearer Scan pro Anfrage. In Datenbanken ist genau das die Begründung für Indizes: einmal sortieren (oder einen Baum-Index bauen), danach O(logn) pro Lookup. Ohne Index wäre jede SELECT-WHERE-Abfrage ein voller Tabellenscan.
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.
Achte auf den Operation-Counter, er zeigt die Wachstumstendenz: n wächst linear, log2n fast nicht.
Probier folgendes:
n = 16, Target in der Mitte: Linear braucht ~8 Vergleiche, Binär nur 1
n = 16, Target ganz hinten: Linear braucht 16 Vergleiche, Binär ~4–5
n = 32, Target nicht im Array: Linear 32, Binär ~5–6 (exakt ⌈log2(n+1)⌉)
Größere n: das Verhältnis wird immer extremer
Lade Visualisierung...
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 ist eine Visualisierung der Wachstumstendenz, n wächst linear, log2n fast nicht. Exakte Werte hängen von Implementierung, Zielposition und Treffer/Nicht-Treffer ab.
Anmelden, um den Fortschritt zu speichern.
Nächster Schritt
Wenn du fertig bist: jetzt üben.
Aktives Abrufen festigt Wissen schneller als nochmal lesen.
Fachliche Qualität
S-Tier · GoldstandardZuletzt geprüft am 18.05.2026
Diese Lerneinheit wurde für typische Bachelor-Klausuren konzipiert. So prüfen wir · Fehler entdeckt? Melde ihn uns oder markiere die fragliche Stelle direkt im Text oben.
Klausur-ÜbersichtKomplette Übersicht: alle Tabs als linearer Text zum Lernen
▾
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).
Teil 1·Erklärung
Übersicht
Linear vs Binär im Vergleich
Lineare Suche und unterscheiden sich vor allem in einer Voraussetzung: Binäre Suche braucht ein sortiertes Array, Lineare Suche nicht. Daraus ergeben sich unterschiedliche Komplexitäten ( vs ) und Anwendungsfälle. Du lernst hier die : Binäre Suche selbst kostet ; falls die Daten vorher sortiert werden müssen, kommt typischerweise Sortieraufwand hinzu. Bei nur einer einzigen Suche lohnt sich das fast nie, bei vielen Suchen ( Suchen mit ungefähr ) klar. Außerdem die wann lineare Suche schneller ist (bei sehr kleinen –, hardware-abhängig, weil Cache-Lokalität und geringere Konstanten-Faktoren die -Vorteile schlagen), und die typische "wann nimmst du was?" mit der Antwort: Sortierungs-Voraussetzung prüfen, Anzahl der Suchen vs Sortier-Kosten abwägen.
Lineare Suche: O(n), keine Voraussetzung, prüft jedes Element der Reihe nach
Binäre Suche: O(log n), Array muss sortiert sein, halbiert den Suchraum bei jedem Schritt
Sortier-Aufwand: Binäre Suche selbst ist O(log n); falls die Daten vorher sortiert werden müssen, kommt typischerweise O(n log n) Sortieraufwand hinzu. Lohnt sich nur bei mehrfachen Suchen
Praxis: bei kleinen oder einmal durchsuchten Datenmengen → Linear; bei großen sortierten Datenmengen oder häufigen Suchen → Binär
In Klausuren wirst du oft gefragt: bei welcher Datenmenge n und welcher Anzahl Suchen lohnt sich Sortieren plus Binäre Suche statt Lineare Suche?.
Break-even-Vergleich (m Suchen in n Elementen):
Wenn das Array bereits sortiert ist: Binäre Suche lohnt sich pro Suche fast immer bei großen n, vergleiche m · n (linear) mit m · log n (binär).
Wenn erst sortiert werden muss: vergleiche m · n (linear ohne Sortieren) mit n log n + m log n (Sortieren + m binäre Suchen). Sortieren plus binäre Suchen lohnt sich also, wenn n log n + m log n < m · n, also wenn m > (n log n)/(n - log n), das ist für große n ungefähr m > log n. Das heißt:m lineare Suchen kosten m · n Vergleiche, m binäre Suchen nur m · log n Vergleiche, plus einmaliges Sortieren. Sind die Daten bereits sortiert oder werden sie dauerhaft sortiert gehalten, entfällt dieser einmalige Sortierblock komplett, dann lohnt sich Binäre Suche pro Lookup direkt.
Konkretes Beispiel (n = 10000):
m (Anzahl Suchen)
Linear: m · n
Sortieren + Binär: n log n + m log n
Wer gewinnt?
m = 1
10 000
≈ 132 877 + 13 ≈ 132 890
Linear
m = 10
100 000
≈ 132 877 + 130 ≈ 133 007
Linear
m = 100
1 000 000
≈ 132 877 + 1 330 ≈ 134 207
Binär (Faktor ~7)
m = 1 000
10 000 000
≈ 132 877 + 13 300 ≈ 146 177
Binär (Faktor ~68)
Break-even liegt hier ungefähr bei m ≈ 14 Suchen, das ist nahe an log₂ 10000 ≈ 13. Bei m < 14 ist eine einmalige lineare Suche pro Query billiger als der Sortier-Aufwand. Diese Rechnung ignoriert konstante Faktoren, in der Praxis verschiebt sich der Break-even leicht je nach Sortieralgorithmus, Hardware und Cache-Verhalten.
Übersicht
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
Der Unterschied in Zahlen
Größenordnung log₂ n vs n (Binär exakt: lceil log₂(n+1) rceil):
n
Linear (Worst)
Binär (~ log₂ n)
Faktor
100
100
~7
~14×
1.024
1.024
11
~93×
1.000.000
1.000.000
20
~50.000×
1 Mrd.
1 Mrd.
30
~33 Mio×
Bei großen sortierten Arrays ist Binäre Suche deutlich schneller als Lineare Suche. Für sehr viele exakte Lookups können Hash-Strukturen mit durchschnittlich O(1) noch besser sein, dafür ohne sortierte Traversierung oder Range-Abfragen.
Wann welcher?
Lineare Suche:
Bei sehr kleinen Arrays kann lineare Suche durch Cache-Lokalität und geringere Konstanten-Faktoren schneller sein. Die genaue Schwelle liegt typisch bei n < 10–30, ist aber hardware-abhängig und gilt ohnehin nur in Mikro-Benchmarks; in Klausuren reicht "kleine Arrays"
Bei unsortierten Daten ohne Sortier-Möglichkeit
Bei einmaligen Suchen, wo der Sortier-Aufwand sich nicht lohnt
Binäre Suche:
Bei großen sortierten Arrays
Bei vielen wiederholten Suchen auf demselben Array
Bei Datenbank-Indizes, B-Bäume/B+-Bäume nutzen sortierte Schlüssel und logarithmische Baumstrukturen, das Prinzip ist ähnlich effizient wie binäre Suche, aber nicht einfach binäre Suche auf einem Array
Was Bibliotheken machen
Java: Arrays.binarySearch() und Collections.binarySearch() setzen sortierte Daten voraus, bei unsortierten Daten ist das Ergebnis undefiniert. Bei Duplikaten ist nicht garantiert, welcher passende Index zurückgegeben wird.
Python: bisect Modul liefert primär Einfügepositionen in sortierten Listen (bisect_left, bisect_right). Für Existenzprüfung danach: pos < len(a) and a[pos] == target.
C++: std::binary_search liefert nur bool. Für die Position des ersten passenden Elements: std::lower_bound.
Aber im Kopf haben muss man beide, sie tauchen in jeder Algorithmik-Klausur auf.
Wann linear trotz O(n) besser ist
Auch wenn binäre Suche asymptotisch klar gewinnt, gibt es Szenarien wo lineare Suche pragmatisch die richtige Wahl ist. Bei sehr kleinen Arrays, oft im niedrigen zweistelligen Bereich, je nach Sprache, Hardware und Datenlayout, sind die Konstanten und die einfache CPU-Pipeline der linearen Suche oft schneller, weil binäre Suche eine Division/Vergleich/Sprung-Logik pro Schritt braucht. Bei unsortierten Daten ohne Sortier-Möglichkeit (z. B. Streaming-Daten, Log-Files) ist binäre Suche schlicht nicht anwendbar. Bei einer einmaligen Suche lohnt sich der Sortieraufwand O(n log n) fast nie, da n Vergleiche linear ohnehin billiger sind als n log n Sortier-Vergleiche.
Wann Sortieren + binär lohnt
Bei vielen Suchen auf demselben Datensatz (m Suchen, m groß) dreht sich das Verhältnis. Sortier-Kosten O(n log n) amortisieren sich über die m Suchen, die danach jeweils O(log n) statt O(n) kosten. Daher die Break-even-Faustregel: ab ungefähr m > log₂ n Suchen wird das Vorsortieren günstiger als ein linearer Scan pro Anfrage. In Datenbanken ist genau das die Begründung für Indizes: einmal sortieren (oder einen Baum-Index bauen), danach O(log n) pro Lookup. Ohne Index wäre jede SELECT-WHERE-Abfrage ein voller Tabellenscan.
Weiter im Tab "Interaktiv" siehst du beide Algorithmen live nebeneinander.
Teil 2·Visualisierung / Interaktiv
Interaktiv
Live-Vergleich
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.
Achte auf den Operation-Counter, er zeigt die Wachstumstendenz: n wächst linear, log₂ n fast nicht.
Probier folgendes:
n = 16, Target in der Mitte: Linear braucht ~8 Vergleiche, Binär nur 1
n = 16, Target ganz hinten: Linear braucht 16 Vergleiche, Binär ~4–5
n = 32, Target nicht im Array: Linear 32, Binär ~5–6 (exakt lceil log₂(n+1) rceil)
Größere n: das Verhältnis wird immer extremer
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 ist eine Visualisierung der Wachstumstendenz, n wächst linear, log₂ n fast nicht. Exakte Werte hängen von Implementierung, Zielposition und Treffer/Nicht-Treffer ab.
Teil 3·Quiz / Klausurfragen
Quiz
Klausurfragen mit Lösungen (6)
F1.Welcher Algorithmus funktioniert auf einem unsortierten Array?
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.
F2.Du hast ein sortiertes Array mit 1.024 Elementen. Ungefähr wie viele Vergleiche mehr braucht Lineare Suche im Worst Case gegenüber Binärer Suche?
Antwort: Etwa 1.000 mehr
Erklärung: Linear: 1024 Vergleiche im Worst Case. Binär: `lceil log₂(1025) rceil = 11` Vergleiche im Worst Case (Faustregel: `log₂ 1024 = 10` Halbierungs-Stufen). Differenz: ungefähr 1.013, also rund 1.000 mehr.
F3.Du suchst einmal in einem unsortierten Array mit 1000 Elementen. Was ist effizienter?
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.
F4.Welche Suche ist im Best Case schneller, wenn das Element gleich beim ersten Vergleich gefunden wird?
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.
F5.Welche Voraussetzung hat binäre Suche, die lineare Suche nicht hat?
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.
F6.Welcher Algorithmus skaliert deutlich besser bei sehr großen Datenmengen (n > 1 Million)?
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.
