Die entscheidende Beobachtung ist, dass die Zahl der zu durchsuchenden Elemente sich bei jedem Schritt halbiert – am Anfang haben wir N Möglichkeiten, danach nur noch N∕2, dann N∕2∕2 = N∕4, also beim n-ten Schritt N∕2ⁿ. Wir haben das Element auf jeden Fall gefunden, wenn wir nur noch ein Element zu durchsuchen haben, sind also fertig, wenn n gerade N∕2ⁿ = 1 oder N= 2ⁿ erfüllt. Logarithmieren auf beiden Seiten liefert ldN= nld2 – mit anderen Worten brauchen wir im schlimmsten Fall lnN Iterationen, binary search hat logarithmische Laufzeit und gehört damit zu den eher “schnellen” Algorithmen.