Izskaidrojiet, kāpēc binārās meklēšanas sarežģītība izteikta caur izpildes laika logaritmu.

Dabiskā meklēšana darbojas sakārtotā masīvā, katrā solī sadalot meklēšanas apgabalu uz pusi. Katru reizi tas izslēdz pusi no atlikušajiem elementiem, tādējādi elementu skaits, kas jā pārbauda, samazinās ģeometriskā progresijā.

Ja sākotnēji mums ir n elementu, pēc pirmā soļa paliek n/2, tad n/4, n/8 un tā tālāk, līdz paliek tikai viens elements. Šo dalījumu skaits ir algoritma soļu skaits un tas ir vienāds ar skaitli k, kuram ir spēkā ( n / 2^k = 1 ).

Risinot vienādojumu, iegūstam:

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

Tādējādi binārās meklēšanas izpildes laiks ir proporcionāls ievades datu lieluma logaritmam, tas ir, (O(\log n)). Tas ir daudz efektīvāk nekā lineārā meklēšana ar (O(n)).