Met binair zoeken wordt een waarde gezocht in 1000 verschillende waarden die oplopend gesorteerd zijn. Eén vergelijking laat zien of de waarden gelijk zijn of dat de ene kleiner of groter is. Wat is het maximale aantal vergelijkingen, voor zowel een geslaagde als een mislukte zoekactie?

Antwoord: A. 10

Elke vergelijking halveert het zoekbereik ongeveer, en 2¹⁰ = 1024 ≥ 1000, dus na hoogstens 10 vergelijkingen is het bereik op (⌊log₂ 1000⌋ + 1 = 10). De tijdcomplexiteit is O(log n), en zelfs voor 1 miljoen waarden zijn hoogstens 20 vergelijkingen nodig. 32 komt overeen met √1000 ≈ 31,6, en 500 ligt dicht bij het gemiddelde van lineair zoeken (ongeveer n/2). Bedenk wel dat binair zoeken gesorteerde gegevens vereist en dat het sorteren zelf O(n log n) kost.