/ Algorithmen & Komplexität

Binäre Suche Schritte

Maximale Anzahl Schritte (Vergleiche) der binären Suche in einem sortierten Array: Schritte = ⌈log₂(n)⌉.

01 · Eingabe

Binäre Suche Schritte berechnen

Maximale Anzahl Schritte (Vergleiche) der binären Suche in einem sortierten Array: Schritte = ⌈log₂(n)⌉.

Lösen für

Schritte = ⌈log₂(n)⌉

n Elementanzahl

Worum geht es?

Die binäre Suche halbiert den Suchbereich in jedem Schritt. In einem sortierten Array mit n Elementen genügen daher höchstens ⌈log₂(n)⌉ Vergleiche, bis das gesuchte Element gefunden oder als nicht vorhanden ausgeschlossen ist.

Die Aufrundung sorgt dafür, dass auch bei nicht-Zweierpotenz-Größen genug Vergleiche eingeplant werden. Das macht die binäre Suche selbst bei Milliarden Einträgen praxistauglich.

Die Formel

Formel Binäre Suche

Schritte = ⌈log₂(n)⌉

Umstellung:
    n = 2^Schritte

Die Variablen

Symbol	Bedeutung	Einheit	Erklärung
n	Elementanzahl	—	Anzahl Elemente im sortierten Array.
Schritte	Max. Schritte	—	Maximale Anzahl Vergleiche.

Minimal-Beispiel

Suche in einem Array mit n = 1 000 000 Einträgen:

Rechnung Suchschritte

Schritte = ⌈log₂(1 000 000)⌉
         = ⌈19,93⌉
         = 20 Vergleiche

Praxis-Beispiele

Beispiel 1 — Telefonbuch

n = 1024 Einträge:

Rechnung Telefonbuch

Schritte = ⌈log₂(1024)⌉
         = 10 Vergleiche

Beispiel 2 — Maximaler Suchraum bei Budget

Wie groß darf n werden, wenn maximal 32 Vergleiche pro Suche zulässig sind?

Rechnung Maximalgröße

n = 2^32
  = 4 294 967 296 ≈ 4,3 · 10⁹

Beispiel 3 — Vergleich zur linearen Suche

n = 10⁹:

Rechnung Vergleich

Lineare Suche:  bis zu 10⁹ Vergleiche
Binäre Suche:   ⌈log₂(10⁹)⌉ = 30 Vergleiche

Faktor: ca. 33 Millionen.