3.2 Binäre Suche

Video

Hinweise zu diesem Video

Korrekturen

Die Korrekturen betreffen das Video. In den Folien zum Herunterladen sind sie eingearbeitet, soweit sie die Folien betreffen.

• Folie 28: Die Regel „log2(n) aufrunden“ stimmt für 20 Elemente, aber nicht allgemein. Richtig ist: log2(n) abrunden und 1 addieren; bei 16 Elementen sind es also höchstens 5 Vergleiche, nicht 4.
• Ton zu Folie 26: Für eine einzige Suche lohnt sich vorheriges Sortieren nicht, denn schon das Sortieren muss jedes Element mindestens einmal ansehen, die lineare Suche höchstens jedes einmal. Sortieren zahlt sich erst aus, wenn mehrfach gesucht wird.

Einordnung

• Welches Element bei gerader Anzahl die Mitte ist, klärt erst Frage 1 der Extra-Minuten (Folie 28): Sie können ab- oder aufrunden, müssen aber dabei bleiben. Das brauchen Sie, um die binäre Suche von Hand durchzuspielen.

Material