Magyarázza el, miért a bináris keresés összetettségét a futási idő logaritmusával fejezzük ki.

A bináris keresés egy rendezett tömbön működik, minden lépésben a keresési területet félbe osztva. Minden lépésben a maradék elemek felét kizárja, így a vizsgálandó elemek száma geometriai sorozatban csökken.

Ha eredetileg n elemünk van, az első lépés után n/2, majd n/4, n/8 és így tovább marad, amíg csak egy elem nem marad. Ezeknek az osztásoknak a száma a lépések száma, és megegyezik azzal a k számmal, amelyre igaz, hogy ( n / 2^k = 1 ).

A egyenlet megoldásával kapjuk:

[ 2^k = n \implies k = \log_2 n ]

Így a bináris keresés futási ideje arányos a bemeneti adatok méretének logaritmusával, vagyis (O(\log n)). Ez sokkal hatékonyabb, mint a lineáris keresés, amely (O(n)) időt igényel.