为什么二分快

二分快在“每步都砍掉一半”。设一共有 $n$ 个数，第一次比完剩 $n/2$，再比剩 $n/4$……直到只剩 $1$ 个。问“$n$ 连续除以 $2$ 几次到 $1$”，答案就是 ${\log }_{2}n$。

$$\underset{{\log }_{2}n\text{ 步}}{n\to \frac{n}{2}\to \frac{n}{4}\to \cdots \to 1}$$

所以二分的复杂度是 $O(\log n)$。$1000$ 个数，因为 $2^{10}=1024>1000$，最多约 $10$ 次就能定位；线性查找最坏要 $1000$ 次。数据越多差距越夸张：$100$ 万个数，线性要百万次，二分只要约 $20$ 次（$2^{20}\approx 10^6$）。

// 直观感受：n 每翻一千倍，二分只多约 10 步
// n=1e3 -> ~10;  n=1e6 -> ~20;  n=1e9 -> ~30

代价是必须先有序。若数据只查一两次，排序的 $O(n\log n)$ 可能比省下的还贵；查询次数多时才值得。