Vysvetlite, prečo sa zložitosť binárneho vyhľadávania vyjadruje pomocou logaritmu času vykonávania.

Binárne vyhľadávanie funguje na zoradenom poli tým, že pri každom kroku rozdelí oblasť vyhľadávania na polovicu. Pri každom kroku vylúči polovicu zostávajúcich prvkov, takže počet prvkov, ktoré je potrebné skontrolovať, klesá v geometrickej postupnosti.

Ak máme na začiatku n prvkov, po prvom kroku zostáva n/2, potom n/4, n/8 a tak ďalej, kým nezostane len jeden prvok. Počet týchto delení je počet krokov algoritmu a je rovný číslu k, pre ktoré platí ( n / 2^k = 1 ).

Riešením rovnice dostaneme:

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

Tým je doba behu binárneho vyhľadávania úmerná logaritmu veľkosti vstupných dát, teda (O(\log n)). To je oveľa efektívnejšie ako lineárne vyhľadávanie s (O(n)).