比较顺序查找、折半查找和分块查找的适用条件与查找长度,掌握折半判定树和分块索引的工作过程。

# 一、查找的基本概念

查找是在记录集合中,根据给定关键字确定是否存在目标记录,并返回其位置或关联数据。若成功,查找长度通常按与关键字进行比较或探测的次数计;失败查找也可能需要若干次比较。

平均查找长度(ASL)是所有可能查找请求所需比较次数的概率加权平均:

ASL⁡=∑i=1rpiCi,\operatorname{ASL}=\sum_{i=1}^{r}p_i C_i,

其中 pip_i 是第 ii 种请求的概率,CiC_i 是相应查找长度。若各记录被查概率相同,成功查找时可对所有记录的查找长度取算术平均。

# 二、顺序查找

顺序查找从头到尾逐个比较,适用于无序表,也可用于有序表。无序表的失败查找必须检查全部 nn 个元素;若 nn 个元素被等概率成功查找,平均比较次数为

ASL⁡成功=1+2+⋯+nn=n+12.\operatorname{ASL}_{成功} =\frac{1+2+\cdots+n}{n} =\frac{n+1}{2}.

1
2
3
4
5
6
7
8
int SequentialSearch(const int data[], int n, int key) {
for (int i = 0; i < n; i++) {
if (data[i] == key) {
return i;
}
}
return -1;
}

最好时间为 O(1)O(1),平均和最坏时间为 O(n)O(n),额外空间为 O(1)O(1)。若数据已经递增有序,当前元素大于目标时可以提前失败;这个优化不改变最坏复杂度。

# 三、折半查找

折半查找(二分查找)要求记录按关键字有序,且存储结构支持随机访问。每次比较中间元素,将候选区间缩小为左半或右半。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int BinarySearch(const int data[], int n, int key) {
int low = 0;
int high = n - 1;

while (low <= high) {
int mid = low + (high - low) / 2;
if (data[mid] == key) {
return mid;
}
if (data[mid] < key) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return -1;
}

每次区间规模约减半,时间复杂度为 O(log⁡n)O(\log n),迭代版本额外空间为 O(1)O(1)。若改成递归,调用栈需要 O(log⁡n)O(\log n) 空间。链表虽有序,但访问中间结点需顺链遍历,通常不适合直接使用折半查找。

折半查找判定树以每次选出的中间记录为结点;较小关键字进入左子树,较大关键字进入右子树。对偶数长度区间,中点可以按题目约定取靠左或靠右的位置;画树时必须沿用代码的取中点规则。查找失败对应落入某个空链接位置,查找长度包括实际比较过的结点数。

# 四、分块查找

分块查找把表分成若干块,块内可以无序,但各块的关键字范围按块次序递增,并维护每块的最大关键字作为索引。查找分两步:

  1. 在索引表中找到第一个最大关键字不小于目标值的块。
  2. 在该块内部进行顺序查找。

flowchart LR
    A[目标关键字] --> B[查找块索引]
    B --> C[确定候选块]
    C --> D[块内顺序查找]

若共有 nn 个元素、每块约有 bb 个元素,则块数约为 n/bn/b。索引若使用顺序查找,平均代价约为 n/(2b)+b/2n/(2b)+b/2;当 bb 取约 n\sqrt n 时,平均查找代价为 O(n)O(\sqrt n)。若索引有序,也可对索引折半查找,再对候选块顺序查找。

分块查找不要求块内有序,但要求块之间有序,并且索引值能正确界定目标所在的候选块。只对整张表 “分组” 而没有块间次序,不能直接使用该查找过程。

# 五、方法对比

方法数据前提平均 / 最坏时间额外空间
顺序查找无序也可O(n)O(n) / O(n)O(n)O(1)O(1)
折半查找有序且能随机访问O(log⁡n)O(\log n) / O(log⁡n)O(\log n)迭代为 O(1)O(1)
分块查找块内无序、块间有序约 O(n)O(\sqrt n)(均衡分块)需维护索引

# 六、考场检查清单

  1. 顺序查找不要求关键字有序,折半查找要求有序且可随机访问。
  2. 二分区间更新时,找到中点后必须排除已经比较过的中点。
  3. 计算 ASL 时先确定是成功还是失败查找,以及各请求是否等概率。
  4. 分块查找先定位块,再查块内元素;两层代价都要计入。
  5. 判定树的形状取决于中点规则,偶数长度区间不能擅自改约定。
更新于 阅读次数 次

请我喝[茶]~( ̄▽ ̄)~*

梦前辈 微信支付

微信支付

梦前辈 支付宝

支付宝