Explica de ce complexitatea căutării binare se exprimă prin logaritmul timpului de execuție.

Căutarea binară funcționează pe un array sortat, împărțind de fiecare dată zona de căutare în două. La fiecare pas, excluderă jumătate din elementele rămase, astfel încât numărul de elemente care trebuie verificate scade în progresie geometrică.

Dacă inițial avem n elemente, după primul pas rămân n/2, apoi n/4, n/8 și tot așa, până când rămâne un singur element. Numărul acestor diviziuni este numărul de pași ai algoritmului și este egal cu numărul k, pentru care ( n / 2^k = 1 ).

Rezolvând ecuația, obținem:

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

Astfel, timpul de execuție al căutării binare este proporțional cu logaritmul dimensiunii datelor de intrare, adică (O(\log n)). Acest lucru este mult mai eficient decât căutarea liniară cu (O(n)).