Linear vs Binär im Vergleich

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(log n)) und Anwendungsfälle. Du lernst hier die Break-even-Analyse: Binäre Suche selbst kostet O(log n); falls die Daten vorher sortiert werden müssen, kommt typischerweise O(n log n) Sortieraufwand hinzu. Bei nur einer einzigen Suche lohnt sich das fast nie, bei vielen Suchen (m Suchen mit m ungefähr ≥ log n) klar. Außerdem die Praxis-Faustregel wann lineare Suche schneller ist (bei sehr kleinen Arrays n < 10–30, hardware-abhängig, weil Cache-Lokalität und geringere Konstanten-Faktoren die log n-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(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):

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

Der Unterschied in Zahlen

Größenordnung log₂ n vs n (Binär exakt: lceil log₂(n+1) rceil):

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.

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

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.