跳转至

408 高频考点精讲:数组查找(Array Search Algorithms)

模块归属:数据结构 · 查找
考点层级:微观细分考点(近十年考查 \(\ge 3\) 次)
适用对象:408 计算机考研备考学生


一、 考情档案

  • 近十年考查频次:4 次(2016~2025 年:2016#9、2023#8、2024#5、2025#7)
  • 历年总考查频次:6 次(含 2010#9、2015#7)
  • 出题形式:全部为单项选择题(分值 2 分)。同时,折半查找思想在综合应用题(如两个等长升序序列寻找中位数、二分搜索答案空间等)中多次作为核心底层逻辑被考查。
  • 命题特点:
  • 物理存储与逻辑特性的严格依赖:考查算法生效的软硬件先决条件,重点甄别物理随机存取特性及逻辑单调性对折半查找的决定性约束(如 2024#5)。
  • 折半判定树的高度与极值推导:考查二叉判定树的高、最大比较次数计算,以及平均查找长度(ASL)的数学推导(如 2010#9、2023#8)。
  • 合法比较序列的收敛性检验:以二叉排序树性质为理论依据,考查查找过程中动态区间的收缩一致性(如 2015#7)。
  • 分块查找的最优参数优化:深入考查索引顺序查找的块长设定、索引结构设计,以及运用均值不等式求解最小 ASL 对应的最优块大小(如 2025#7)。
  • 算法时间开销对比:考查跳跃顺序查找、顺序查找相比折半查找在特定数据分布场景下的比较次数优势(如 2016#9)。
近十年考查年份分布:
2016   2017   2018   2019   2020   2021   2022   2023   2024   2025
 √      -      -      -      -      -      -      √      √      √
(#9)                                             (#8)   (#5)   (#7)

二、 具体考察内容

(1) 顺序查找实现:普通查找及带哨兵查找

顺序查找又称线性查找(Linear Search),适用于无序或有序的线性表(顺序表或链表)。

  • 无哨兵实现: 每次循环需进行两次逻辑判定:一是数组下标越界检查(i >= 0 或 i < n),二是当前关键字匹配判断(A[i] == key)。

    int Search_Seq(int A[], int n, int key) {
        for (int i = 0; i < n; i++) {
            if (A[i] == key) return i; // 查找成功
        }
        return -1; // 查找失败
    }
    

  • 带哨兵实现(优化判定开销): 将待查关键字放置在数组边界保留位置(通常为下标 0 处的 A[0]),从表尾(下标 \(n\))向表头反向扫描。

    typedef struct {
        int *elem; // 存储空间基址,0号单元留空作为哨兵
        int length;
    } SSTable;
    
    int Search_Seq_Sentinel(SSTable ST, int key) {
        ST.elem[0] = key; // 设置哨兵
        int i = ST.length;
        while (ST.elem[i] != key) {
            i--;
        }
        return i; // 若返回0说明查找失败,若返回1~length则查找成功
    }
    
    哨兵机制价值:由于 ST.elem[0] 必然等于 key,while 循环体内无需设立下标防越界检查条件(无需判断 i >= 0),使循环内部的比较指令减少一半。在海量数据检索时能有效提高执行效率。

(2) 顺序查找的平均查找长度(ASL)推导

设顺序表长度为 \(n\),每个元素的查找概率等可能,即: $\(P_i = \frac{1}{n} \quad (1 \le i \le n)\)$

  • 查找成功时的平均查找长度: 查找到第 \(i\)$ \text{个元素所需比较次数为} $\(C_i = n - i + 1\)$ \text{(反向扫描)或} $\(C_i = i\)(正向扫描): $\(\text{ASL}_{\text{succ}} = \sum_{i=1}^{n} P_i C_i = \frac{1}{n} \sum_{i=1}^{n} i = \frac{1}{n} \cdot \frac{n(n + 1)}{2} = \frac{n + 1}{2}\)$

  • 查找失败时的平均查找长度: 若查找失败,算法必须扫描全部 \(n\)$ \text{个有效数据并与哨兵比较,总计比较} $\(n + 1\) 次: $\(\text{ASL}_{\text{unsucc}} = n + 1\)$ 注:若采用无哨兵且不计下标越界比较的抽象模型,失败时的关键字比较次数为 \(n\) 次。

(3) 有序顺序表的顺序查找优化

若顺序表中的关键字已按单调递增排列,当查找一个不存在的关键字时,无需遍历整个表。

  • 提前终止原则: 若扫描过程中遇到第一个大于待查关键字 \(key\)$ \text{的元素} $\(A[i]\)$ \text{(即} $\(A[i] > key\)),即可直接判定查找失败并终止程序。
  • 有序表查找判定树: 将查找过程对应一棵二叉判定树。树中共有 \(n\)$ \text{个内部圆形结点(代表查找成功),以及} $\(n + 1\) 个外部方形结点(代表查找失败落入的各个区间): $\(I_0 = (-\infty, k_1), \quad I_1 = (k_1, k_2), \quad \dots, \quad I_{n-1} = (k_{n-1}, k_n), \quad I_n = (k_n, +\infty)\)$
  • 有序表查找失败的平均查找长度: 落入区间 \(I_0\)$ \text{只需比较 1 次,落入区间} $\(I_1\)$ \text{需比较 2 次,……,落入区间} $\(I_{n-1}\)$ \text{需比较} $\(n\)$ \text{次,落入区间} $\(I_n\)$ \text{(大于表尾最大值)需扫描至末尾比较} $\(n\) 次。 设落入各失败区间的概率均等为 \(Q_j = \frac{1}{n + 1}\): $\(\text{ASL}_{\text{unsucc}} = \frac{1}{n + 1} \left( \sum_{j=1}^{n} j + n \right) = \frac{1}{n + 1} \left( \frac{n(n + 1)}{2} + n \right) = \frac{n}{2} + \frac{n}{n + 1}\)$ 当 \(n \to \infty\)$ \text{时,} $\(\text{ASL}_{\text{unsucc}} \approx \frac{n}{2} + 1\)$ \text{,相比无序表失败时的} $\(n + 1\) 次比较,平均效率提升近一倍。

(1) 生效的两个充分必要前提

折半查找(又称二分查找)的高效性建立在对候选区间进行对半排除的基础之上。实施折半查找必须同时满足以下两个先决条件,缺一不可:

  1. 逻辑结构前提:关键字严格有序
    线性表中的元素必须按关键字单调递增或单调递减排列。若表无序,中间位置关键字的大小无法作为区间剪枝的依据。
  2. 物理存储前提:必须采用顺序存储结构(具备随机存取特性)
    存储结构必须支持在 \(O(1)\) 时间复杂度内根据逻辑序号直接计算出物理地址并访问元素(如连续数组空间)。
典型数据结构适配性深度辨析:
  • 顺序存储的有序数组:满足有序性与随机存取特性,完全适合直接折半查找。
  • 无序数组:具备随机存取,但无单调性,无法剪枝排除半数区间,不适合。
  • 单链表(含按值排好序的有序单链表):虽具逻辑单调性,但存储物理离散,访问第 \(\lfloor(low+high)/2\rfloor\)$ \text{个中间结点必须从头指针开始逐个指针迭代遍历,耗时} $\(O(n)\)。若强行使用折半逻辑,总时间复杂度退化为: $\(T(n) = T\left(\frac{n}{2}\right) + O(n) = O(n)\)$ 完全失去了折半查找降维至对数阶的优势,不适合。
  • 静态链表(含逻辑有序的静态链表):静态链表物理上虽存储于一段连续数组中,但结点的逻辑后继完全由各结点的游标指针(cur)串联维持。数组物理下标 \(mid\)$ \text{上的元素与逻辑顺序上的第} $\(mid\) 个结点没有任何对应关系。要在静态链表中查找逻辑中点,同样必须沿游标链遍历,不适合直接使用折半查找。

(2) 经典折半查找算法实现

采用闭区间 \([low, high]\) 设计模式:

int Binary_Search(int A[], int n, int key) {
    int low = 0, high = n - 1;
    while (low <= high) {
        // 防止数据溢出,等价于 (low + high) / 2
        int mid = low + (high - low) / 2;
        if (A[mid] == key) {
            return mid; // 查找成功
        } else if (A[mid] > key) {
            high = mid - 1; // 缩小至左半区间 [low, mid - 1]
        } else {
            low = mid + 1;  // 缩小至右半区间 [mid + 1, high]
        }
    }
    return -1; // low > high,查找失败
}

(3) 折半查找判定树(Decision Tree)的核心定理

折半查找的过程可以用一棵二叉树来直观描述,该树被称为折半查找判定树。 树中的每个内部结点表示一次成功的关键字比较(用圆形表示,标注数组下标或关键字);每个叶子结点的空指针外延表示一次查找失败的判定状态(用矩形表示,代表区间范围)。

定理 1:判定树平衡性及拓扑形态
  • 定理表述:任意长度为 \(n\) 的有序顺序表对应的折半查找判定树必为一棵平衡二叉树(AVL 树)。
  • 证明要点: 对于区间 \([low, high]\)$ \text{,元素总数为} $\(m = high - low + 1\)。 选取中间元素 \(mid = \lfloor (low + high)/2 \rfloor\) 作为根结点。 左子树元素区间为 $[low, mid

  • 1]$$ \text{,元素个数为} $$m_L = mid

  • low = \lfloor (m

  • 1)/2 \rfloor$。 右子树元素区间为 \([mid + 1, high]\)$ \text{,元素个数为} $$m_R = high

  • mid = m

  • 1

  • m_L = \lceil (m

  • 1)/2 \rceil$。 左右子树包含的结点数相差满足: $\(0 \le m_R - m_L \le 1\)$ 由于子树同样递归执行该划分规则,左右子树的高度差必满足 \(|\Delta h| \le 1\)。故判定树必为平衡二叉树。

定理 2:向下取整及向上取整的形态特征
  • 若取 \(mid = \lfloor (low + high)/2 \rfloor\)(向下取整): 当子表中元素个数为偶数时,\(m_R - m_L = 1\),即右子树结点数比左子树结点数恰好大 1。
  • 若取 \(mid = \lceil (low + high)/2 \rceil\)(向上取整): 当子表中元素个数为偶数时,\(m_L - m_R = 1\),即左子树结点数比右子树结点数恰好大 1。
定理 3:判定树高度及最大比较次数推导
  • 定理表述:含有 \(n\)$ \text{个结点的折半查找判定树,其树高} $\(h\)(根结点深度规定为 1)为: $\(h = \lceil \log_2(n + 1) \rceil = \lfloor \log_2 n \rfloor + 1\)$
  • 代数推导: 高度为 \(h\) 的平衡二叉判定树所能容纳的最多结点数对应一棵满二叉树,即: $\(N_{\max} = 2^h - 1\)$ 高度为 \(h\)$ \text{的判定树,其结点数必然大于高度为} $\(h - 1\) 的满二叉树容量,即: $\(2^{h-1} - 1 < n \le 2^h - 1\)$ 两端加 1 得到: $\(2^{h-1} < n + 1 \le 2^h\)$ 两边同时取以 2 为底的对数: $\(h - 1 < \log_2(n + 1) \le h \implies h = \lceil \log_2(n + 1) \rceil\)$ 由整除取整性质,\(\lceil \log_2(n + 1) \rceil \equiv \lfloor \log_2 n \rfloor + 1\)。
  • 物理意义: 折半查找在最坏情况下(无论查找成功还是查找失败)关键字之间的比较次数严格等于判定树的高度 \(h\)。 任何折半查找的比较次数均不可能超过 \(\lfloor \log_2 n \rfloor + 1\)。
定理 4:内部结点及外部结点的度数关联
  • 含有 \(n\)$ \text{个元素的有序表,判定树拥有} $\(n\) 个圆形内部结点。
  • 拥有 \(n + 1\)$ \text{个矩形外部结点(失败结点),代表由} $\(n\)$ \text{个关键字在数轴上划分出的} $\(n + 1\) 个互斥失败开区间。
  • 所有的失败结点(外部结点)必然只出现在判定树的最底两层(即第 \(h\)$ \text{层与第} $\(h + 1\) 层)。
判定树结构图示(以 n = 11 为例,向下取整):
                         6
                     /       \
                   3           9
                 /   \       /   \
                1     4     7     10
               / \   / \   / \   /  \
             [0] [1][2][3][4][5][6]  11
                                    /  \
                                  [7]  [8]
(其中圆圈为元素下标 1~11,方框 [0]~[11] 为外部失败区间)

(4) 平均查找长度(ASL)严格推导

设各元素查找概率相等(\(P_i = \frac{1}{n}\)$ \text{),各失败区间概率均等(} $\(Q_j = \frac{1}{n + 1}\))。 第 \(k\)$ \text{层的内部结点数记为} $\(m_k\)。

  • 查找成功的平均查找长度: $\(\text{ASL}_{\text{succ}} = \frac{1}{n} \sum_{i=1}^{n} l_i = \frac{1}{n} \sum_{k=1}^{h} k \cdot m_k\)$ 当 \(n = 2^h - 1\)(判定树为满二叉树)时: $\(\sum_{k=1}^{h} k \cdot 2^{k-1} = (h - 1)2^h + 1\)$ 代入得: $$\text{ASL}_{\text{succ}} = \frac{(h

  • 1)2^h + 1}{2^h

  • 1} = \frac{n + 1}{n} \log_2(n + 1)

  • 1 \approx \log_2(n + 1)

  • 1$$ 时间复杂度为 \(O(\log_2 n)\)。

  • 查找失败的平均查找长度: 注意:在判定树模型中,到达第 \(l'_j\)$ \text{层的外部失败结点时,实际所执行的有效关键字比较次数为其双亲结点的层数,即} $\(l'_j - 1\)。 $\(\text{ASL}_{\text{unsucc}} = \frac{1}{n + 1} \sum_{j=1}^{n + 1} (l'_j - 1)\)$ 当判定树为满二叉树形态时,所有 \(n + 1\)$ \text{个外部结点均处于第} $\(h + 1\)$ \text{层,故每次失败均比较} $\(h\) 次: $\(\text{ASL}_{\text{unsucc}} = h = \log_2(n + 1)\)$

(5) 合法折半查找序列判定准则(区间单调收敛性)

在给定的数组范围内,若给定一串关键字比较序列 \(\langle c_1, c_2, \dots, c_m \rangle\),判定其是否能够构成折半查找的实际比较序列。

  • 收敛区间迭代准则: 初始化全局有效开区间为 \((L_{\min}, R_{\max}) = (-\infty, +\infty)\)。 对于序列中任意相邻的两个比较值 \(c_i\)$ \text{与} $\(c_{i+1}\):
  • 若 \(c_{i+1} > c_i\)$ \text{:意味着目标关键字大于} $\(c_i\)$ \text{,下一轮必在右子树查找,区间下界收紧为} $\(L_{\min} = c_i\);
  • 若 \(c_{i+1} < c_i\)$ \text{:意味着目标关键字小于} $\(c_i\)$ \text{,下一轮必在左子树查找,区间上界收紧为} $\(R_{\max} = c_i\);
  • 判定铁律:序列中的每一个后续元素 \(c_k\)(\(k > i\)$ \text{)都必须严格落在当前的有效区间} $\((L_{\min}, R_{\max})\) 之内。一旦某后继元素落在了已排他的区间之外,则该序列绝对不可能由折半查找产生。

(1) 数据组织架构

分块查找又称索引顺序查找,吸收了顺序查找与折半查找的优点,其数据结构由两级构成: 1. 主表(数据表): 将长度为 \(n\)$ \text{的主表划分为} $\(b\) 个子表(块)。主表必须满足“块间有序,块内无序”(亦可块内有序,但从动态维护成本考虑,块内通常无序)。 - 块间有序定义:后一块中所有元素的关键字均大于(或等于)前一块中所有元素的最大关键字。 2. 索引表(Index Table): 为每个分块在索引表中建立一个索引项。每个索引项由两部分构成: - max_key:本块中的最大关键字; - addr:本块在主表中的起始地址(指针或起始下标)。 - 索引表按 max_key 呈严格单调递增排列。

分块查找结构示意:
索引表(有序):
+---------+------+------+------+
| max_key |  18  |  35  |  68  |
+---------+------+------+------+
| addr    |  &B1 |  &B2 |  &B3 |
+---------+------+------+------+
             |      |      |
             v      v      v
主表(块内无序,块间有序):
块 1 (B1): [12, 8, 18, 14]      (全部 <= 18)
块 2 (B2): [25, 35, 20, 22]     (全部 > 18 且 <= 35)
块 3 (B3): [45, 68, 50, 60]     (全部 > 35 且 <= 68)

(2) 查找操作的两阶段机制

分块查找分为互相关联的两个阶段: * 第一阶段:在索引表中查找目标所在的分块
由于索引表按关键字有序,既可采用顺序查找,亦可采用折半查找。 目标是找到满足 \(\text{key} \le \text{Index}[i].\text{max\_key}\)$ \text{的最小索引下标} $\(i\)。 * 第二阶段:在确定的分块内查找目标关键字
由于块内元素无序,只能采用顺序查找。

(3) 平均查找长度(ASL)与极值推导

设主表元素总数为 \(n\)$ \text{,将主表均匀划分为} $\(b\)$ \text{块,每块包含} $\(s\) 个元素,满足约束条件: $\(n = b \cdot s \iff b = \frac{n}{s}\)$ 设主表中每个元素的查找概率等均(\(P = \frac{1}{n}\))。 分块查找的平均查找长度等于确定块的平均查找长度与块内查找的平均查找长度之和: $\(\text{ASL} = \text{ASL}_I + \text{ASL}_S\)$

情况 1:索引表顺序查找,块内顺序查找
  • 索引表包含 \(b\)$ \text{个项,顺序查找确定块的平均查找长度为} $\(\text{ASL}_I = \frac{b + 1}{2}\);
  • 块内包含 \(s\)$ \text{个元素,顺序查找命中元素的平均查找长度为} $\(\text{ASL}_S = \frac{s + 1}{2}\);
  • 综合平均查找长度: $\(\text{ASL} = \frac{b + 1}{2} + \frac{s + 1}{2} = \frac{b + s}{2} + 1 = \frac{\frac{n}{s} + s}{2} + 1\)$
最优块长及最小 ASL 的代数推导(均值不等式):

根据柯西-施瓦茨 / 算术-几何均值不等式(AM-GM 不等式): 对任意正实数 \(\frac{n}{s}\)$ \text{与} $\(s\),有: $\(\frac{n}{s} + s \ge 2\sqrt{\frac{n}{s} \cdot s} = 2\sqrt{n}\)$ 当且仅当两项相等,即: $\(\frac{n}{s} = s \implies s^2 = n \implies s = \sqrt{n}\)$ 时取等号。 * 推论 1(最优参数):当每块元素个数 \(s = \sqrt{n}\)$ \text{,分块数} $\(b = \sqrt{n}\) 时,分块查找的平均查找长度取得全局最小值。 * 推论 2(最小 ASL):代入最优块长,取得的最小平均查找长度为: $\(\text{ASL}_{\min} = \frac{2\sqrt{n}}{2} + 1 = \sqrt{n} + 1\)$ * 复杂度分析:最优情况下分块查找的时间复杂度为 \(O(\sqrt{n})\)$ \text{,介于顺序查找} $\(O(n)\)$ \text{与折半查找} $\(O(\log n)\) 之间。

情况 2:索引表折半查找,块内顺序查找

当索引表规模较大时,在索引表中采用折半查找以提高效率: $\(\text{ASL}_I \approx \lceil \log_2(b + 1) \rceil\)$ 综合平均查找长度为: $\(\text{ASL} \approx \lceil \log_2(b + 1) \rceil + \frac{s + 1}{2}\)$

索引表折半落点判定规则(高频陷阱): 若在索引表中采用折半查找且目标关键字未恰好匹配某个块的最大值,折半查找将在 \(low > high\) 时结束。 此时,\(low\) 所指向的索引项即为目标元素可能存在的对应块。 - 若 \(low \le b\)$ \text{:转向} $\(low\) 所指示的块继续执行顺序查找; - 若 \(low > b\):说明待查关键字严格大于索引表中所有块的最大关键字,直接断定全表查找失败,无需再进入块内扫描。


4. 三大静态查找算法横向对比矩阵

评估维度 顺序查找(无序表) 顺序查找(有序表) 折半查找 分块查找(两阶段顺序)
平均时间复杂度 \(O(n)\) \(O(n)\) \(O(\log_2 n)\) \(O(\sqrt{n})\)
最大比较次数 \(n\)$ \text{(或带哨兵} $\(n+1\)) \(n\) \(\lfloor \log_2 n \rfloor + 1\) \(b + s = \frac{n}{s} + s\)
逻辑有序性要求 无要求(无序/有序) 必须严格有序 必须严格有序 块间有序,块内无序
物理存储结构 顺序表或单链表 顺序表或单链表 仅限支持随机存取的顺序表 顺序表(索引表与主表可混用)
动态插入新项成本 \(O(1)\)$ \text{(直接插入末尾) } $\(O(n)\)$ \text{(维护顺序位移) } $\(O(n)\)$ \text{(需后移大量元素) } $\(O(1)\)$ \text{或} $\(O(s)\)(定位块后直接尾插)
适用业务场景 小型数据、链式存储、无序表 链表有序、失败率高的环境 静态稠密数据表、高频海量查询 兼顾动态更新与中高频检索系统

三、 近十年真题精讲(2016~2025)


【真题 1】2025 年 408 统考第 7 题 · 分块查找最优块长计算

题目
已知查找表中有 400 个元素,查找元素概率相同。采用分块查找法且均匀分块。若采用顺序查找法确定元素所在块,且块内也采用顺序查找法,为效率最高,每块包含元素应为( )。
A. 8          B. 10          C. 20          D. 25

【解析】

  1. 建立代数模型: 设元素总数 \(n = 400\)$ \text{。表被均匀划分为} $\(b\)$ \text{块,每块包含} $\(s\) 个元素,满足关系式: $\(b \cdot s = 400 \implies b = \frac{400}{s}\)$
  2. 构建目标函数(平均查找长度 ASL): 题目指定:确定块采用顺序查找,块内亦采用顺序查找。 各元素查找概率均等,故: $\(\text{ASL}_I = \frac{b + 1}{2}, \quad \text{ASL}_S = \frac{s + 1}{2}\)$ 综合平均查找长度: $\(\text{ASL} = \text{ASL}_I + \text{ASL}_S = \frac{b + s}{2} + 1 = \frac{\frac{400}{s} + s}{2} + 1\)$
  3. 极值推导: 为使检索效率最高,即寻求 \(\text{ASL}\) 取得最小值。由均值不等式定理: $\(\frac{400}{s} + s \ge 2\sqrt{\frac{400}{s} \cdot s} = 2\sqrt{400} = 2 \times 20 = 40\)$ 等号成立的充分必要条件为: $\(\frac{400}{s} = s \implies s^2 = 400 \implies s = 20\)$ 此时分块数 \(b = \frac{400}{20} = 20\)。 最小平均查找长度为 \(\text{ASL}_{\min} = \frac{20 + 20}{2} + 1 = 21\)。 因此,每块应包含 20 个元素。

正确答案:C


【真题 2】2024 年 408 统考第 5 题 · 折半查找物理结构适配性甄别

题目
下列数据结构中,不适合直接使用折半查找的是( )。
I. 有序链表      II. 无序数组      III. 有序静态链表      IV. 无序静态链表
A. 仅 I、II          B. 仅 II、IV          C. 仅 I、II、IV          D. I、II、III、IV

【解析】

折半查找(Binary Search)生效的两个必要基石为:“逻辑单调有序” 与 “物理支持随机存取”。逐项剖析各结构: * 分析 I(有序链表): 逻辑上有序,但物理存储采用动态离散的单链表节点,仅支持顺序存取。定位逻辑中间节点 \(\lfloor(low+high)/2\rfloor\)$ \text{无法在} $\(O(1)\)$ \text{时间内由下标直接计算得出,必须从头指针遍历} $\(O(n)\)$ \text{步。折半操作蜕化,整体复杂度反降为} $\(O(n)\),丧失二分精髓,故不适合直接使用折半查找。 * 分析 II(无序数组): 物理上支持通过数组下标在 \(O(1)\) 时间随机存取,但表中数据无序,中间位置元素无法判定目标值落在左半部还是右半部,二分剪枝逻辑彻底失效,故不适合直接使用折半查找。 * 分析 III(有序静态链表): 静态链表利用一维数组作为底层物理容器,然而其逻辑前驱与后继顺序完全由游标指针(数组元素内保存的下一个元素物理下标)维持。物理连续存储并不等同于逻辑连续,数组下标 \(mid = (low + high)/2\) 处的元素绝非逻辑排序序列的中位数。查找中间元素仍需顺沿游标指针逐步遍历,无法实现按逻辑序号直接折半跳转,故不适合直接使用折半查找。 * 分析 IV(无序静态链表): 既不满足逻辑有序性,又无法支持逻辑序号的随机存取,两个先决条件均被打破,显然不适合。

综上所述,I、II、III、IV 四种数据结构均无法直接实施折半查找。

正确答案:D


【真题 3】2023 年 408 统考第 8 题 · 折半查找最大比较次数严格推导

题目
对含有 600 个元素的有序顺序表进行折半查找,关键字之间的比较次数最多是( )。
A. 9          B. 10          C. 30          D. 300

【解析】

  1. 理论映射: 有序顺序表的折半查找过程严格对应一棵二叉判定树。 关键字比较次数最多的情境对应于:
  2. 查找失败,到达最深层的外部失败结点;
  3. 或者查找成功,但目标关键字恰好位于判定树的最深一层叶子内部结点。 因此,关键字之间的最多比较次数严格等于该判定树的高度 \(h\)。
  4. 树高公式计算: 对于含有 \(n\) 个结点的折半查找判定树,其高度公式为: $$ \text{h = \lfloor \log_2 n \rfloor + 1 \quad \text{或} \quad h = \lceil \log_2(n + 1) \rceil} $$
  5. 代入数值计算: 已知元素个数 \(n = 600\)。 考察 2 的整数次幂边界: $\(2^9 = 512, \quad 2^{10} = 1024\)$ 由于 \(512 < 600 < 1024\),可得: $\(\lfloor \log_2 600 \rfloor = 9\)$ 因此树高为: $\(h = 9 + 1 = 10\)$ (若采用第二种公式校验:\(n + 1 = 601\),\(512 < 601 \le 1024 \implies \lceil \log_2 601 \rceil = 10\))。 故关键字之间的比较次数最多为 10 次。

正确答案:B


【真题 4】2016 年 408 统考第 9 题 · 跳跃顺序查找相比折半查找的比较开销权衡

题目
在有 \(n\)(\(n > 1000\)$ \text{)个元素的升序数组} $\(A\)$ \text{中查找关键字} $\(x\)。查找算法的伪代码如下所示。

k = 0;
while (k < n && A[k] < x) k = k + 3;
if (k < n && A[k] == x) 查找成功;
else if (k - 1 < n && A[k - 1] == x) 查找成功;
else if (k - 2 < n && A[k - 2] == x) 查找成功;
else 查找失败;
本算法与折半查找算法相比,有可能具有更少比较次数的情形是( )。
A. 当 \(x\) 不在数组中
B. 当 \(x\) 接近数组开头处
C. 当 \(x\) 接近数组结尾处
D. 当 \(x\) 位于数组中间位置

【解析】

  1. 分析题给算法机制: 该算法是一种步长(Step)为 3 的跳跃顺序查找法(Jump Search)。
  2. 从下标 \(k = 0\)$ \text{开始,以 3 为跨度向后跳跃跃进(依次检查} $\(A[0], A[3], A[6], \dots\));
  3. 一旦遇到 \(A[k] \ge x\) 或越界,跳出 while 循环;
  4. 随后在微观区间 \(\{k, k-1, k-2\}\) 内执行最多 3 次等值比较以确定是否命中。
  5. 比较次数对比剖析:
  6. 场景:\(x\)$ \text{非常接近数组开头处(例如} $\(x\)$ \text{为} $\(A[0]\)$ \text{或} $\(A[1]\)):
    • 跳跃查找算法:在 \(k = 0\)$ \text{时执行 1 次条件比较,随后进入 if 判断执行 1~2 次比较即可成功命中,总比较次数仅为常数级(约 2~3 次),与} $\(n\) 的规模完全无关。
    • 折半查找算法:首次比较必定从全局中点 \(mid \approx \lfloor n/2 \rfloor \approx 500\)$ \text{开始。为了不断向左逼近数组开头,必须连续经历多次区间对半缩小。对于} $\(n > 1000\)$ \text{,到达数组最前端区域需要经历近} $\(\lfloor \log_2 1000 \rfloor \approx 9\) 到 10 次比较。
    • 结论:在此场景下,跳跃算法的比较次数远少于折半查找。
  7. 场景:\(x\) 不在数组中:
    • 若 \(x\)$ \text{大于所有元素,跳跃算法需扫描整个数组,执行约} $\(n/3\) 次比较;折半查找仅需最多 10 次比较。
  8. 场景:\(x\) 接近数组结尾处:
    • 跳跃算法需要经历约 \(n/3 > 333\) 次循环跳转;而折半查找仍只需约 10 次比较。
  9. 场景:\(x\) 位于中间位置:
    • 跳跃算法需经历约 \(n/6 \approx 166\) 次跳转;折半查找首次比较即中或仅需常数次。

综上所述,当目标元素极度贴近数组起始位置时,跳跃顺序查找表现出显著优于折半查找的局部性能。

正确答案:B


四、 核心解题套路与易错陷阱

1. 折半查找判定树规范构造法(防错模版)

在各类考题中,常要求依据给定顺序表画出对应的判定树。 * 规则 1:中点取整规则确定
408 考研及统编教材中,若无特殊声明,一律默认采用向下取整法: $\(mid = \lfloor (low + high) / 2 \rfloor\)$ * 规则 2:节点数奇偶分支特征
- 若区间元素个数为奇数,划分后左右子树结点数严格相等; - 若区间元素个数为偶数,划分后左子树比右子树少 1 个结点(即右子树结点数 \(N_R = N_L + 1\))。 * 判定树构建实例(以元素下标 \(1 \sim 7\) 为例): - \([1, 7]\):\(mid = 4\)$ \text{,根为 4;左区间} $\([1, 3]\)$ \text{,右区间} $\([5, 7]\); - \([1, 3]\):\(mid = 2\),左孩子为 2;其左右分别为 1 和 3; - \([5, 7]\):\(mid = 6\),右孩子为 6;其左右分别为 5 和 7; - 构造结果为一棵高度为 3 的满二叉树。

2. 折半查找比较序列合法性排查:“区间排除法”

此类题目的典型代表为历年真题(如 2015 年第 7 题):给出四个由关键字构成的比较序列,甄别何者不可能为折半查找序列。

  • 标准化解题四步法:
  • 初始化边界:设全局合法区间为 \((-\infty, +\infty)\)。
  • 设定目标趋向:根据序列后继数字相比前序数字的增减,确定是在左子树还是右子树。
  • 收缩区间边界:
    • 后继数比当前数大 \(\implies\) 抛弃当前数及其左侧,下界抬升至当前数;
    • 后继数比当前数小 \(\implies\) 抛弃当前数及其右侧,上界压低至当前数。
  • 越界违例核验:检查后续所有待比较数字是否完好保持在最新界定的闭/开区间内。一旦发现某个后续数字突破了之前收缩形成的边界,该序列立刻判定为非法。
经典实战演示(判定序列:500, 200, 450, 180 是否合法):
第 1 步:比较 500。区间处于 (-inf, +inf)。
第 2 步:后继比较 200(200 < 500)。表明目标在 500 左侧,有效范围收缩为 (-inf, 500)。
第 3 步:后继比较 450(450 > 200)。表明目标在 200 右侧,有效范围进一步收缩为 (200, 500)。
第 4 步:后继比较 180。
        核验:此时有效区间已被封锁在 (200, 500) 之内!
        数字 180 < 200,完全掉落在有效区间之外!
        结论:该序列必然非法!在判定树上不可能出现向左跨越祖先结点的回退现象。

3. 分块查找索引表采用折半查找的落点陷阱

考生最容易混淆的盲点:在索引表中折半查找时,若待查关键字不等于任何一个块的 max_key,究竟应进入哪个分块?

  • 避坑法则: 在常规升序索引表中,各块记录的是该块的最大关键字。 因此,目标关键字只要小于等于某块的最大关键字,且严格大于上一块的最大关键字,该目标就必然属于这一块。 当折半查找循环终止(即 \(low > high\))且未精确命中某块 max_key 时:
  • 此时 \(low\) 所指向的索引块正是第一个 max_key 大于待查关键字的块!
  • 必须转入 \(low\) 所指向的块进行块内顺序查找。
  • 若此时 \(low > b\)(超出了索引表界限),则直接宣布查找失败(全表中无任何元素能大于等于该关键字)。

五、 考点速记清单

  1. 二分两前提:逻辑有序排列,物理随机存取(链表、无序数组、静态链表皆不可)。
  2. 树高及最大比较次数:\(n\)$ \text{个结点的判定树高度为} $\(h = \lfloor \log_2 n \rfloor + 1 = \lceil \log_2(n + 1) \rceil\)$ \text{;无论成功失败,最大比较次数恒为} $\(h\)。
  3. 判定树拓扑性质:
  4. 折半查找判定树必是 AVL 平衡二叉树;
  5. 内部成功结点 \(n\)$ \text{个,外部失败结点} $\(n + 1\) 个;
  6. 外部结点仅分布在最底两层(第 \(h\)$ \text{层与第} $\(h + 1\) 层)。
  7. 向下取整中点律:若采用 \(mid = \lfloor (low + high) / 2 \rfloor\),偶数节点区间必是左小右大(右子树结点数 = 左子树结点数 + 1)。
  8. 分块查找最优极值:
  9. 均匀分块下,两阶段顺序查找的 \(\text{ASL} = \frac{n/s + s}{2} + 1\);
  10. 最优块长为 \(s^* = \sqrt{n}\)$ \text{,最优分块数} $\(b^* = \sqrt{n}\);
  11. 对应最小平均查找长度为 \(\text{ASL}_{\min} = \sqrt{n} + 1\)。
  12. 带哨兵优势:哨兵存放在 elem[0],免去每轮循环对下标越界的重复判断,显著削减机器指令开销。
  13. 序列合法排查诀窍:区间只能单向收敛,后继比较值若跃出前面所收缩的开区间 \((L_{\min}, R_{\max})\),该序列立判非法。