7.1 顺序查找、折半查找与分块查找

查找的基本概念与平均查找长度，顺序查找、折半查找（判定树）以及分块查找的过程与效率分析。

查找的基本概念

顺序查找

顺序查找又称线性查找，它对顺序表和链表都是适用的。

一般线性表的顺序查找

从线性表的一端开始，逐个检查关键字是否满足给定的条件。

typedef struct {
    ElemType *elem;         // 动态数组基址，0 号单元留空作为"哨兵"
    int TableLen;
} SSTable;
int Search_Seq(SSTable ST, ElemType key) {
    ST.elem[0] = key;       // 哨兵
    int i;
    for (i = ST.TableLen; ST.elem[i] != key; --i);   // 从后往前找
    return i;               // 若查找失败，则返回 0
}

• 查找成功：$\mathrm{ASL}_\text{成功} = \sum_{i=1}^{n} \frac{1}{n}(n - i + 1) = \dfrac{n+1}{2}$
• 查找失败：各关键字的比较次数总是 $n + 1$ 次（包含与哨兵的比较），$\mathrm{ASL}_\text{失败} = n + 1$

有序表的顺序查找

若在查找之前就已经知道表是关键字有序的，则查找失败时可以不用再比较到表的另一端就能返回查找失败的信息。例如表中关键字从小到大排列，查找到第 $i$ 个元素时发现它大于 key，就可以确定查找失败。

用判定树描述有序线性表的查找过程：树中的圆形结点表示有序线性表中存在的元素；矩形结点称为失败结点，若有 $n$ 个结点，则相应地有 $n + 1$ 个查找失败结点。

折半查找

折半查找又称二分查找，它仅适用于有序的顺序表。

基本思想：首先将给定值 key 与表中中间位置的元素比较，若相等，则查找成功，返回该元素的存储位置；若不等，则所需查找的元素只能在中间元素以外的前半部分或后半部分。然后在缩小的范围内继续进行同样的查找。

1int Binary_Search(SSTable L, ElemType key) {
2    int low = 0, high = L.TableLen - 1, mid;
3    while (low <= high) {
4        mid = (low + high) / 2;         // 取中间位置
5        if (L.elem[mid] == key)
6            return mid;                 // 查找成功则返回所在位置
7        else if (L.elem[mid] > key)
8            high = mid - 1;             // 从前半部分继续查找
9        else
10            low = mid + 1;              // 从后半部分继续查找
11    }
12    return -1;                          // 查找失败，返回 -1
13}

判定树

折半查找的过程可用判定树来描述：树中每个圆形结点表示一个记录，结点中的值为该记录的关键字值；树中最下面的叶结点都是方形的，它表示查找失败的区间。从判定树可以看出：

• 查找成功时的比较次数为从根结点到该结点的路径上的结点数（即该结点的层数）；
• 查找失败时的比较次数为从根结点到对应失败结点的父结点的路径上的结点数；
• 每个结点值均大于其左子结点值，且均小于其右子结点值；若有序序列有 $n$ 个元素，则对应的判定树有 $n$ 个圆形的非叶结点和 $n + 1$ 个方形的叶结点；
• 显然，判定树是一棵平衡二叉树。若 mid = ⌊(low + high)/2⌋，则对于任意结点，必有：右子树结点数 − 左子树结点数 = 0 或 1。

分块查找

分块查找又称索引顺序查找，它吸取了顺序查找和折半查找各自的优点，既有动态结构，又适于快速查找。

基本思想：将查找表分为若干子块。块内的元素可以无序，但块间的元素是有序的，即第一个块中的最大关键字小于第二个块中的所有记录的关键字，以此类推。再建立一个索引表，索引表中的每个元素含有各块的最大关键字和各块中的第一个元素的地址，索引表按关键字有序排列。

分块查找的过程分为两步：第一步是在索引表中确定待查记录所在的块，可以顺序查找或折半查找索引表；第二步是在块内顺序查找。

设索引查找和块内查找的平均查找长度分别为 $L_I$、$L_S$，则 $\mathrm{ASL} = L_I + L_S$。将长度为 $n$ 的查找表均匀地分为 $b$ 块，每块有 $s$ 个记录，在等概率情况下：

• 若在块内和索引表中均采用顺序查找，则 $\mathrm{ASL} = \dfrac{b+1}{2} + \dfrac{s+1}{2} = \dfrac{s^2 + 2s + n}{2s}$。此时若 $s = \sqrt{n}$，则平均查找长度取最小值 $\sqrt{n} + 1$；
• 若对索引表采用折半查找，则 $\mathrm{ASL} = \lceil \log_2(b+1) \rceil + \dfrac{s+1}{2}$。

即时练习