Was ist Binäre Suche (Binary Search)?

Antwort: B. Die Daten müssen nach dem Schlüssel sortiert sein

Die binäre Suche entscheidet anhand des Vergleichs mit dem mittleren Element, ob der Zielwert in der vorderen oder hinteren Hälfte liegt, und halbiert den Bereich. Dieser Schluss gilt nur, weil die Daten sortiert sind; auf ein unsortiertes Array lässt sich die binäre Suche nicht anwenden. Die Zahl der Elemente muss keine Zweierpotenz sein; wählt man die Mitte zum Beispiel als (untere Grenze + obere Grenze) ÷ 2 abgerundet, funktioniert sie bei jeder Größe. Doppelte Werte sind ebenfalls kein Problem: Einer der passenden Werte wird gefunden (um das erste Vorkommen zu finden, ist ein kleiner Zusatzschritt nötig).

Antwort: A. 10

Jeder Vergleich halbiert den Suchbereich ungefähr, und es gilt 2¹⁰ = 1024 ≥ 1000; nach höchstens 10 Vergleichen ist der Bereich also erschöpft (⌊log₂ 1000⌋ + 1 = 10). Die Komplexität ist O(log n), und selbst bei 1 Million Werten genügen höchstens 20 Vergleiche. 32 entspricht √1000 ≈ 31,6, und 500 liegt nahe am Mittelwert einer linearen Suche (etwa n/2). Zu beachten ist allerdings, dass die binäre Suche sortierte Daten braucht und das Sortieren selbst O(n log n) kostet.