顺序查找与折半查找¶

线性查找 | Linux C 编程一站式学习

折半查找 | Linux C 编程一站式学习

二分查找 | Hello 算法

静态查找表上, 408 常考三种方法: 顺序查找不要求有序, 从头扫到尾; 折半查找要求有序顺序表, 每步砍掉一半; 分块查找介于二者之间, 用索引先定位到某一块.

衡量效率用平均查找长度 \(ASL = \sum p_i c_i\), 默认每个元素等概率, \(p_i = 1/n\).

顺序查找¶

顺序查找（Sequential Search）, 又称线性查找, 从线性表的一端起, 逐个把关键字和给定值比较, 直到命中或走到另一端. 顺序表和链表都能用, 因为它只需要遍历整个表.

一般线性表的顺序查找¶

无序表只能这么查, 因为没有任何先验信息帮你跳过元素. 顺序表按值查找和链表按值查找都是顺序查找. 若问的不是某个给定值, 而是第 \(k\) 小, 则可以采用顺序统计量.

以 \(\{8, 3, 9, 2, 5\}\) 找 \(2\) 为例, 从左往右:

8  3  9  2  5      8 != 2
   3  9  2  5      3 != 2
      9  2  5      9 != 2
         2  5      2 == 2, 成功, 比较 4 次

哨兵¶

每走一步既要比较关键字, 又要判断下标有没有出界. 408习惯把待查关键字放进 \(A[0]\) 当哨兵（sentinel）, 从表尾往回走. 即使表里没有这个值, 也一定会在 \(A[0]\) 停住, 循环条件只剩「关键字相不相等」.

typedef struct {
    ElemType *elem;   /* elem[0] 给哨兵, 数据在 elem[1..length] */
    int length;
} SSTable;

int search_sequential(SSTable ST, ElemType key) {
    ST.elem[0] = key;
    int i;
    for (i = ST.length; ST.elem[i] != key; --i)
        ;
    return i;         /* 0 表示失败 */
}

哨兵只是加速循环, 不改变渐近复杂度, 也不能拿 \(A[0]\) 当普通数据用. 这和直接插入排序里 \(A[0]\) 的用法同理.

算法分析¶

等概率时, 成功找到第 \(i\) 个元素要比较 \(c_i = n - i + 1\) 次 (从表尾走; 从表头走则 \(c_i = i\), ASL 相同):

失败时必走完整表, 再撞上哨兵, \(ASL_{失败} = n+1\). 最好 \(O(1)\), 最坏 / 平均都是 \(O(n)\). 空间 \(O(1)\).

有序表的顺序查找¶

表已按关键字递增排好时, 仍是逐个比较, 但失败可以提前停, 一旦碰到 \(A[i] > key\), 后面只会更大, 也就无需再比较了.

找 \(4\) 于 \(\{2, 3, 5, 8, 9\}\):

2  3  5  8  9      2 < 4, 继续
   3  5  8  9      3 < 4, 继续
      5  8  9      5 > 4, 失败 (不用看 8, 9)

成功时每个元素仍可能出现在任一位置, \(ASL_{成功}\) 还是 \((n+1)/2\).

失败时有 \(n+1\) 个「空隙」(比最小还小, 夹在相邻两元素之间, 比最大还大). 从左往右扫, 比较次数分别是 \(1, 2, \ldots, n, n\), 等概率则

\(n\) 较大时大约是无序失败的一半, 但数量级仍是 \(O(n)\). 有序本身换不来对数时间; 那是下面折半查找的事.

折半查找¶

折半查找（Binary Search）, 又称二分查找. 是一种在有序数组中查找特定元素的算法. 它通过将数组分成两部分, 并比较中间元素与目标值, 从而缩小查找范围, 直到找到目标值或确定目标值不存在.

一个序列能应用折半查找, 必须同时满足两个前提:

1. 表必须有序 (下面默认递增)

2. 必须能 \(O(1)\) 随机访问中点, 因此只适用于顺序表, 不适用于链表

每次取当前区间中点, 目标要么就是它, 要么只可能在左半, 要么只可能在右半. 搜索范围按 \(1/2,\ 1/4,\ 1/8,\ \ldots\) 缩小, 所以是 \(O(\log n)\).

以 \(\{1, 3, 4, 6, 7, 8, 10, 13, 14\}\) 找 \(8\) (low / high 用括号标出当前闭区间, ^ 标中点):

[1  3  4  6  7  8  10  13  14]     mid=7 < 8, 去右半
             ^
             [8  10  13  14]       mid=10 > 8, 去左半
                 ^
             [8]                   mid=8, 命中
              ^

找 \(5\): 区间会缩到空 (low > high), 返回失败.

算法实现¶

408 习惯 \(1\) 下标, 数据在 \(A[1..n]\):

int binary_search(SSTable ST, ElemType key) {
    int low = 1, high = ST.length, mid;
    while (low <= high) {
        mid = (low + high) / 2;
        if (ST.elem[mid] == key)
            return mid;
        else if (ST.elem[mid] > key)
            high = mid - 1;     /* 左半 [low, mid-1] */
        else
            low = mid + 1;      /* 右半 [mid+1, high] */
    }
    return 0;                   /* 失败 */
}

\(0\) 下标写法把 low 初值改成 \(0\), high 改成 \(n-1\) 即可, 循环条件仍是 low <= high (闭区间).

循环不变式¶

和直接插入排序一样, 可以用循环不变式说明「循环停了就对了」.

这里的判断是:

若 key 在表里, 则它一定还在闭区间 \(A[\textit{low}..\textit{high}]\) 中. 区间以外已经排除.

1. 初始化: 进入循环前 \([\textit{low}, \textit{high}]\) 就是整张表, 显然成立. 这要求 Caller 保证表有序, 否则「中点偏小则右半才可能有」推不出来

2. 保持: \(A[mid] < key\) 时, 有序性推出 \(A[\textit{low}..mid]\) 都偏小, 新区间 \([mid+1,\ \textit{high}]\) 仍包含答案 (若存在); 偏大则对称地缩到左边

3. 终止: low > high 时区间为空. 空区间之外就是整张表, 故表中没有 key

递归写法的 Base Case 是区间为空或中点命中, 递推是「只在半边继续」; 和循环是同一套推理.

判定树¶

把每次比较的中点画成结点, 得到一棵判定树: 左孩子是「往左半继续」, 右孩子是「往右半继续」. 它本身满足二叉排序树的顺序.

\(n=7\) 的有序表 \(\{1,2,3,4,5,6,7\}\), mid = (low+high)/2 对应:

            4
         /     \
       2         6
      / \       / \
     1   3     5   7
    / \ / \   / \ / \
    □ □ □ □   □ □ □ □

方框是失败时落到的外部结点, 共 \(n+1\) 个, 对应 \(n+1\) 个空隙. 内部结点上的层号就是成功时的比较次数.

\(n = 2^h - 1\) 时判定树是满二叉树, 高 \(h = \log_2(n+1)\). 一般的 \(n\), 高是 \(\lfloor \log_2 n \rfloor + 1\), 树平衡, 但不一定是完全二叉树. 例如 \(n=10\) 时根是第 \(5\) 个元素, 左右子树规模 \(4\) 和 \(5\), 底层不是从左往右填满的.

算法分析¶

成功 ASL 是判定树内部结点深度的平均值. \(n=7\) 时

满树时有公式

失败则走到外部结点, 满树时比较次数都是 \(h\), \(ASL_{失败} = \log_2(n+1)\).

• 时间最好 \(O(1)\) (一击中的), 最坏 / 平均 \(O(\log n)\). 这是比较查找在有序数组上最坏情况的最优量级

• 迭代空间 \(O(1)\); 递归还要 \(O(\log n)\) 调用栈

• 只适用于顺序表. 链表上找中点本身要 \(O(n)\), 折半的优势没了

动态场景下要边插边查, 维持整表有序太贵 (插入 \(O(n)\)), 改用显式的二叉排序树或散列表.

折半思想的应用¶

普通折半的核心思想在于想要查找的元素若存在则还在当前区间, 取中点比较一次, 丢掉不含答案的那一半.

应用时主要留意:

• 变的是区间是什么

• 比较的是什么

• 相等时需要不需要继续查找相等子序列的边界, 需要的话往哪边缩

查边界¶

普通折半有个特点: 如果待查找的元素在数组中有多个则返回其中任意一个.

有时候, 我们并不希望这样, 而是希望找到序列中相等元素第一次或最后一次出现的位置, 比如在折半插入排序中, 我们希望插入点落在相等元素的右侧(即该元素最后出现的位置后), 从而保证排序的稳定.

这时候, 我们可以在找到带查找元素后仍往左或往右缩, 直到找到边界:

• 相等也令 high = mid - 1: 停住后 low 是第一个 \(\ge key\) 的位置. 该处等于 key 就是最左出现.

• 相等也令 low = mid + 1: 停住后 high 是最后一个 \(\le key\) 的位置, 即最右出现.

不变式改成: 若 key 存在, 则它的第一次出现一定还在 \([\textit{low}, \textit{high}]\) 里.

\(\{1, 2, 2, 2, 5, 6, 8, 9\}\) 找 \(2\), 相等也往左(第一次出现):

[1  2  2  2  5  6  8  9]     mid=3 == 2, 继续左半
          ^
[1  2  2]                    mid=1 == 2, 继续左半
    ^
[1]                          mid=0 < 2, 去右, 区间空
→ low=1, 即 a[1]

也可以命中时看左邻: mid == 0 或 a[mid-1] != key 就确认最左, 否则 high = mid - 1. 和「相等也往左」都是 \(O(\log n)\); 多一次下标判断, 踩在最左元素上能提前停. mid == 0 必须写在前面, 否则会读 a[-1].

int binary_search_first_occ(int *arr, int n, int key)
{
    assert(is_sorted(arr, n));

    int left = 0;
    int right = n - 1;

    while (left <= right) {
        int mid = (left + right) / 2;

        if (arr[mid] >= key) {  /* 相等也往左 */
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }

    if (left < n && arr[left] == key) { /* 是否命中 */
        return left;
    }
    return -1;
}

值域上折半¶

将折半的思想应用到数学问题中, 比如求 \(y\) 的正平方根, 它落在一段有界实数区间里, 对中点 \(x\) 比较的是 \(x^2\) 和 \(y\):

• \(x^2 < y\): 根在右半, low = x

• \(x^2 > y\): 根在左半, high = x

连续区间不能写成 mid ± 1, 否则会跳过根. 端点直接收到中点, 长度每次减半.

\(y \ge 1\) 时根在 \([0, y]\); \(0 < y < 1\) 时 \(\sqrt{y} > y\) (例如 \(\sqrt{0.25}=0.5\)), 应搜 \([0, 1]\). 统一取 \([0,\ \max(1, y)]\). 「从 0 到 \(y\)」对小于 1 的数不成立.

浮点几乎碰不到精确相等, 终止条件改成精度: \(|x^2-y|<\varepsilon\), 并加上 high - low 足够小, 以免 \(\varepsilon\) 小于当前数量级的 ulp 时死循环. 迭代次数约 \(\log_2((high-low)/\varepsilon)\), 由区间长度和精度决定, 不是表长 \(n\).

double binary_sqrt(double n, double acc)
{
    assert(n >= 0 && acc > 0);

    double left = 0;
    double right = n < 1 ? 1 : n; /* n < 1 时根在 (n, 1] */
    double est;

    do {
        est = (left + right) / 2;
        if (est * est < n) {
            left = est;
        } else {
            right = est;
        }
    } while (right - left > acc && fabs(est * est - n) > acc);

    return est;
}

指数上折半¶

\(x^n\) 的朴素连乘是 \(\Theta(n)\) 次乘法.

采用折半的思想就可以将时间复杂度降低到 \(O(\log n)\) 次乘法:

必须先算一次 \(x^{\lfloor n/2 \rfloor}\) 再平方. 写成两次 pow(x, n/2) * pow(x, n/2), 递推变成 \(T(n)=2T(n/2)+O(1)=\Theta(n)\), 和连乘同阶.

double binary_pow(double base, int exponent)
{
    assert(exponent >= 0);

    if (exponent == 0) {
        return 1;
    }

    double half = binary_pow(base, exponent / 2);
    if (exponent % 2 == 0) {
        return half * half;
    }
    return half * half * base;
}

\(T(n)=T(\lfloor n/2\rfloor)+O(1)=\Theta(\log n)\), 递归栈同阶.

循环版看 \(n\) 的二进制: base 反复自乘得到 \(x,\ x^2,\ x^4,\ \ldots\), 某一位是 1 就把当前 base 乘进答案, 例如 \(x^{13}=x^8\cdot x^4\cdot x^1\). 额外空间 \(O(1)\):

double binary_pow(double base, int exponent)
{
    assert(exponent >= 0);

    double result = 1;
    while (exponent > 0) {
        if (exponent % 2 == 1) {
            result *= base;
        }
        base *= base;
        exponent /= 2;
    }
    return result;
}

分块查找¶

分块查找（Block Search）, 又称索引顺序查找. 把表切成若干块, 块内不要求有序, 但块与块之间递增: 第 \(i\) 块的最大关键字小于第 \(i+1\) 块的最小关键字. 另建一张索引表, 每项记下该块的最大关键字和起始下标.

查找表   [22, 12, 13 | 38, 29, 36 | 50, 49, 42]
索引表    max=22, 起 0   max=38, 起 3   max=50, 起 6

查 \(29\): 先在索引里走 (顺序或折半), \(22 < 29 \le 38\), 锁定第 \(2\) 块; 再在块内顺序查找, 碰到 \(29\).

索引表有序且很小, 块内无序所以插删只需在块内挪, 不必维持整表有序. 这是它相对折半的主要好处.

设 \(n\) 个元素分成 \(b\) 块, 每块 \(s = n/b\) 个, 块内和索引都用顺序查找, 等概率时

\(s = b = \sqrt{n}\) 时最短, \(ASL_{min} \approx \sqrt{n}+1\), 量级 \(O(\sqrt{n})\). 索引改折半则

块长要在「索引短」和「块内扫得少」之间折中; 块数随数据涨时, 可能再对某块分裂, 类似浅浅一层的B 树思想.

三种方法对照¶