直接推导

设问题规模为 $n$，需要 $t$ 次查找，由二分查找的过程可知，每一次查找问题规模减半，最差情况下，直到问题规模为 1 时才找到或者仍未找到，因此可知：

$$n \times \left(\frac{1}{2}\right) ^t = 1$$

则：

$$2^t = n$$

两边取 $\log$，得

$$t = \log_{2}{n}$$

主定理

在算法分析中，支配理论（英语：master theorem）提供了用渐近符号（大O符号）表示许多由分治法得到的递推关系式的方法。这种方法最初由Jon Bentlery，Dorothea Haken和James B. Saxe在1980年提出，在那里被描述为解决这种递推的“天下无敌法”(master method)。此方法经由经典算法教科书Cormen，Leiserson，Rivest和Stein的《算法导论》 (introduction to algorithm) 推广而为人熟知^[1]https://zh.wikipedia.org/wiki/主定理。不过，并非所有递推关系式都可应用支配理论。

假设有递归关系式 $T(n) = aT\left(\dfrac{n}{b}\right) + f(n)$，其中 $a \geq 1 \mbox{, } b > 1$，其中，$n$为问题规模，$a$为递归的子问题数量，$\dfrac{n}{b}$为每个子问题的规模（假设每个子问题的规模基本一样），$f(n)$为递归以外进行的计算工作。

$f(n)$ 为函数，$T(n)$ 为非负整数，则有以下结果（分类讨论）：

1. 如果存在常数$\epsilon > 0$，有 $f(n) = O\left( n^{\log_b (a) - \epsilon} \right)$（可不严谨的視作多项式地小于）则 $T(n) = \Theta\left( n^{\log_b a} \right)$
2. 如果存在常数$\epsilon\ge0$，有 $f(n) = \Theta\left( n^{\log_b a} \log^{\epsilon} n \right)$ 则 $T(n) = \Theta\left( n^{\log_b a} \log^{\epsilon+1} n \right)$
3. 如果存在常数$\epsilon > 0$，有 $f(n) = \Omega\left( n^{\log_b (a) + \epsilon} \right)$（多项式地大于） 同时存在常数$c < 1$以及充分大的$n$，满足 $a f\left( \dfrac{n}{b} \right) \le c f(n)$ 则 $T\left(n \right) = \Theta \left(f \left(n \right) \right)$

简化版主定理

由于主定理公式十分复杂，计算时可以使用简化版本^[2]https://hunterhug.github.io/goa.c/#/basic/master_method。

若算法的运行时间 $T(n) \le aT\left(\dfrac{n}{b}\right) + \ O(n^d)$，其中 $a \ge 1$ 是子问题个数，$b \ge 1$是输入规模减小的倍数，$d \ge 0$ 是递归过程之外的步骤的时间复杂度指数，则：

$$T\left(n\right) = \begin{cases}
\ O\left(n^d\log{}{n}\right) & a = b^d
\\
\ O\left(n^d\right) & a \lt b^d
\\
\ O\left(n^{\log_{b}{a}}\right) & a \gt b^d
\end{cases}$$

主定理应用

算法	a	b	d	情况	复杂度
二分查找	1	2	0	$a = b^{d}$	$\ O(\log{}{n})$
快速排序	2	2	1（计算分区索引的复杂度为$\ O(n)$）	$a = b^{d}$	$\ O(n\log{}{n})$
归并排序	2	2	1 （合并操作的复杂度为 $\ O(n)$）	$a = b^{d}$	$\ O(n\log{}{n})$

logn算法的优势

可以看到差距非常大，随着问题规模增大，$\log_{2}{n}$ 算法增长的非常缓慢。$2^{10} = 1024$， $2^{20} \approx 100 0000$，问题规模 100 万的时候，$\ O(n)$ 算法需要 100万次，而 $\ O(\log{}{n})$ 只需要 20 次。