14.4.3 二分查找

二分查找也叫折半查找。它的前提是表中元素有序，并且能够快速访问中间位置。课程中用递归代码讲二分查找，重点是上下界变化。

基本过程

设查找区间为 [a,b]，中间位置：

$$m=\lfloor \frac{a+b}{2}\rfloor$$

1. 若 a > b，区间为空，查找失败。
2. 若 L[m] == x，查找成功。
3. 若 x > L[m]，到右半区间 [m+1,b] 查找。
4. 若 x < L[m]，到左半区间 [a,m-1] 查找。

int binarySearch(int L[], int a, int b, int x) {
    if (a > b) return -1;
    int m = (a + b) / 2;
    if (L[m] == x) return m;
    if (x > L[m]) return binarySearch(L, m + 1, b, x);
    return binarySearch(L, a, m - 1, x);
}

课程提醒：中间位置 m 已经比较过，下一轮不能再包含它，否则可能死循环。

复杂度

每次查找都把规模减半：

$$n,\frac{n}{2},\frac{n}{4},...,1$$

所以时间复杂度为：

$$O({\log }_{2}n)$$

与顺序查找对比

比较项	顺序查找	二分查找
是否要求有序	不要求	要求
是否要求随机访问	不要求	要求
最坏时间复杂度	$O(n)$	$O(\log n)$
插入维护成本	低	若需保持有序，插入成本高

本节例题

单选

有序表升序排列，二分查找中若 `x > L[m]`，下一轮应查找：

A[a,b]B[a,m]C[m,b]D[m+1,b]

自查清单

1. 能否写出二分查找失败条件 a > b？
2. 能否正确更新左半区间和右半区间？
3. 能否解释为什么二分查找是分治思想？