已知一个长度为 16 的顺序表 L，其元素按关键字有序排列。若采用折半查找法查找一个 L 中不存在的元素，则关键字的比较次数最多是（ ）。
目标
通过 2009～2025 年的 6 道 408 选择题，检查自己能否准确处理顺序查找、分块查找与折半查找的前提条件、比较次数与判定树高度。
完成后应能：
- 写出顺序、分块和折半查找各自成立的前提与比较次数；
- 由折半判定树高度推算失败查找的最多比较次数；
- 判断一种存储结构或查找序列能否用折半查找；
- 由最优块长理解分块查找两级代价的权衡。
前置知识
建议先阅读 8.1 基础查找与折半查找，并复习 8.2 节二叉排序树中"查找路径"的对比视角。
环境、输入与预期输出
- 环境：任意现代浏览器；建议准备纸笔，用于画折半判定树。
- 输入：本页按年份排列的 6 道单项选择题。
- 预期输出：一份独立作答记录，以及每道错题的错误原因和正确推理。
作答方法
- 阅读题面后点击一个选项，先写下选择依据；
- 点击"提交答案"，再核对对错、正确答案和题解；
- 做错的题点击"重新作答"后再次推导，直到能说明其余选项为什么不成立；
- 完成全部题目后再使用页面末尾的答案总览复核，避免只记答案字母。
选择题
答题进度已答 0/6正确 0
难度基础考点折半查找、比较序列标识
search-408-2015-q07下列选项中，不能构成折半查找中关键字比较序列的是（ ）。
难度进阶考点顺序查找、折半查找、比较次数标识
search-408-2016-q09在有 A[k]、A[k-1]、A[k-2]。本算法与折半查找相比，有可能具有更少比较次数的情形是（ ）。
c
k = 0;
while (k < n && A[k] < x) k = k + 3;
if (k < n && A[k] == x) success;
else if (k - 1 < n && A[k - 1] == x) success;
else if (k - 2 < n && A[k - 2] == x) success;
else fail;难度基础考点折半查找、比较次数标识
search-408-2023-q08对含有 600 个元素的有序顺序表进行折半查找，关键字之间的比较次数最多是（ ）。
难度基础考点折半查找、存储结构标识
search-408-2024-q05下列数据结构中，不适合直接使用折半查找的是（ ）。
I. 有序链表
II. 无序数组
III. 有序静态链表
IV. 无序静态链表
难度基础考点分块查找、最优块长标识
search-408-2025-q07已知查找表中有 400 个元素，各元素查找概率相同。采用均匀分块查找，使用顺序查找确定元素所在块，块内也使用顺序查找。为使效率最高，每块应包含（ ）个元素。
答案总览（建议完成全部题目后查看）
- 第 1 题：B
- 第 2 题：A
- 第 3 题：B
- 第 4 题：B
- 第 5 题：D
- 第 6 题：C
完成清单
思考题
- 为什么折半查找同时要求"有序"和"随机访问"，缺一不可？
- 分块查找的两级顺序查找，代价为什么近似正比于
s + n/s？ - 顺序查找在什么情况下反而是比折半查找更合理的选择？
复盘
- 我是否混淆了"最多比较次数"和"平均比较次数"？
- 哪道题我靠记结论作答，而没有回到判定树或上下界推导？
- 分块查找的块长权衡里，我在哪一步最容易被"块越细越好"的直觉带偏？