7.2.2 折半查找
## 7.2.2 折半查找 折半查找也称二分查找，它仅适用于关键字有序的顺序表。 ### 等级图12 分析对比给定查找算法与折半查找的效率（2016） 折半查找的基本思想：① 首先将给定值 key 与表中中间位置的元素进行比较，若相等，则查找成功，返回该元素的存储位置；② 若不相等，则待查元素只能位于中间元素以外的前半部分或后半部分（例如，当表按升序排列时，若 key 大于中间元素，则待查元素只可能在后半部分），随后在缩小的范围内重复上述过程，直到找到目标元素，或确定表中不存在该元素为止。此时返回查找失败信息。算法实现如下：在选取中间结点时，既可以采用向下取整，也可以采用向上取整。但每次查找必须采用相同的取整方式。相关内容可结合本节习题进一步理解。 ### 等级图13 折半查找的查找路径的判断（2015） 例如，已知 11 个元素的有序表 $\{7, 10, 13, 16, 19, 29, 32, 33, 37, 41, 43\}$，要查找值为 11 和 32 的元素，指针 low 和 high 分别指向当前查找区间的下界和上界，mid 指向中间位置 $[\mathrm(low} + \mathrm{high}) / 2]$。下面说明查找 11 的过程（查找 32 的过程请读者自行分析）： 第一次查找时，将中间位置元素与 key 比较。因为 $11 < 29$，故待查元素若存在，必在区间 [low, mid-1] 内，令 $\mathrm{high} = \mathrm{mid} - 1 = 5$，$\mathrm{mid} = (1 + 5) / 2 = 3$，第二次查找区间为 [1, 5]。 第二次查找时，将中间位置元素与 key 比较。因为 $11 < 13$，故待查元素若存在，必在区间 $[\mathrm{low}, \mathrm{mid} - 1]$ 内，令 $\mathrm{high} = \mathrm{mid} - 1 = 2$，$\mathrm{mid} = (1 + 2) / 2 = 1$，第三次查找区间为 [1, 2]。 第三次查找时，将中间位置元素与 key 比较。因为 $11 > 7$，故待查元素若存在，必在区间 $[\mathrm{mid} + 1, \mathrm{high}]$ 内。令 $\mathrm{low} = \mathrm{mid} + 1 = 2$，$\mathrm{mid} = (2 + 2) / 2 = 2$，第四次查找区间为 [2, 2]。int Binary Search(SSTable L,ElemType key) { int low = 0, high = L.TableLen - 1, mid; while (low &lt;= high) { mid = (low + high) / 2; //取中间位置 if (L.elem[mid] == key) return mid; //查找成功则返回所在位置 else if (L.elem[mid] &gt; key) high = mid - 1; //从前半部分继续查找 else low = mid + 1; //从后半部分继续查找 } return -1; //查找失败，返回 -1 }本算法与折半查找算法相比，有可能具有更少比较次数的情形是（ ）。 A. 当 $\times$ 不在数组中 B. 当 $\times$ 接近数组开头处 C. 当 $\times$ 接近数组结尾处 D. 当 $\times$ 位于数组中间位置 23. 【2017 统考真题】下列二义树中，可能成为折半查找判定树（不含外部结点）的是（ ）。 A.7 10 13 16 19 29 32 33 37 41 43 low! ! high mid <!-- page: 280 --> 2027年数据结构考研复习指导 第四次查找，此时子表仅含一个元素，且 $10 \neq 11$，因此表中不存在待查元素，查找失败。 **考点退后** ▶ 分析给定二叉树树形能否构成折半查找判定树（2017） 折半查找的过程可用图7.2所示的判定树来描述，圆形结点表示表中存在的记录，结点值为其关键字；最底层的方形结点为失败结点，表示查找失败的区间。从判定树可以看出：查找成功时的查找长度等于从根结点到目的结点的路径上的结点数；查找失败时的查找长度等于从根结点到对应失败结点的父结点的路径上的结点数。该判定树满足性质：任一结点的值大于其左子树中所有结点的值，小于其右子树中所有结点的值。若有序表包含 $n$ 个元素，则对应的判定树有 $n$ 个圆形非叶结点和 $n + 1$ 个方形叶结点。显然，该判定树是一棵平衡二叉树（见7.3.2节）。 </pre> <p class="kb-source-missing">原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。</p> <pre class="kb-transcript"> 图7.2 描述折半查找过程的判定树 **考点退后** ▶ 折半查找的最多比较次数的分析（2010、2023） 由上述分析可知，折半查找的比较次数最多不超过判定树的高度。在等概率查找的情况下，查找成功的平均查找长度为 $$ \mathrm {A S L} = \frac {1}{n} \sum_ {i = 1} ^ {n} l _ {i} = \frac {1}{n} (1 \times 1 + 2 \times 2 + \dots + h \times 2 ^ {k - 1}) = \frac {n + 1}{n} \log_ {2} (n + 1) - 1 \approx \log_ {2} (n + 1) - 1 $$ 其中，$h$ 为树的高度。当元素个数为 $n$ 时，树高 $h = \lceil \log_2(n + 1) \rceil$。因此，折半查找的时间复杂度为 $O(\log_2 n)$，平均效率显著高于顺序查找。 以图7.2所示的判定树为例（对应11个元素），查找成功的平均查找长度为 $\mathrm{ASL} = (1\times 1 + 2\times 2 + 3\times 4 + 4\times 4) / 11 = 3$，查找失败的平均查找长度为 $\mathrm{ASL} = (3\times 4 + 4\times 8) / 12 = 11 / 3$。 **考点退后** ▶ 折半查找的适用场景（2024） 由于折半查找需要能够随机访问任意位置的元素，以便快速定位中间元素并缩小区间，因此它仅适用于顺序存储结构，不适用于链式存储结构，且要求表中元素按关键字有序排列。 ## 7.2.3 分块查找 分块查找也称索引顺序查找，它吸取了顺序查找和折半查找各自的优点，既有良好的动态性，又支持较快的查找效率。 分块查找的基本思想是：将查找表划分为若干子块。块内元素可以无序，但块间必须有序，即任意前一块的最大关键字小于后一块中的所有关键字。同时，建立一个索引表，其中每个元素包含对应块的最大关键字和该块的起始地址，且索引表按最大关键字有序排列。 **考点退后** ▶ 分块查找的效率分析（2025） 分块查找过程分为两步：第一步在索引表中确定待查记录所在的块（可采用顺序查找或折半 <!-- page: 281 --> 第7章 查找 269 查找）；第二步在目标块内进行顺序查找。 例如，关键码集合为{88, 24, 72, 61, 21, 6, 32, 11, 8, 31, 22, 83, 78, 54}，可按关键码值24, 54, 78, 88将其划分为4个块，并建立相应的索引表，如图7.3所示。 </pre> <p class="kb-source-missing">原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。</p> <pre class="kb-transcript"> 图7.3 分块查找示意图 分块查找的平均查找长度等于索引查找的平均长度与块内查找的平均长度之和。设索引查找和块内查找的平均查找长度分别为 $L_{1}$ 和 $L_{S}$，则分块查找的平均查找长度为 $$ \mathrm {A S L} = L _ {1} + L _ {\mathrm {S}} $$ 若将长度为 $n$ 的查找表均匀地分为 $b$ 块，每块包含 $s$ 个记录（ $n = bs$ ），并在等概率假设下对索引表和块内均采用顺序查找，则平均查找长度为 $$ \mathrm {A S L} = L _ {1} + L _ {\mathrm {S}} = \frac {b + 1}{2} + \frac {s + 1}{2} = \frac {s ^ {2} + 2 s + n}{2 s} $$ 此时，当块大小 $s$ 取最优值（ $s = \sqrt{n}$ ），则平均查找长度达到最小值 $\sqrt{n} + 1$ 。 尽管索引表占用了额外的存储空间，且索引查找引入了一定的系统开销，但由于分块结构限制了块内查找的范围，分块查找的总体效率仍显著优于普通的顺序查找。 ## 7.2.4 本节试题精选 ### 一、单项选择题 01. 顺序查找适合于存储结构为（）的线性表。 A. 顺序存储结构或链式存储结构 B. 散列存储结构 C. 索引存储结构 D. 压缩存储结构 02. 由 $n$ 个数据元素组成的两个表：一个递增有序，一个无序。采用顺序查找算法，对有序表从头开始查找，发现当前元素已不小于待查元素时，停止查找，确定查找不成功，已知查找任意一个元素的概率是相同的，则在两种表中成功查找（）。 A. 平均时间后者小 B. 平均时间两者相同 C. 平均时间前者小 D. 无法确定 03. 对长度为 $n$ 的有序单链表，若查找每个元素的概率相等，则顺序查找表中任意一个元素的查找成功的平均查找长度为（）。 A. $n / 2$ B. $(n + 1) / 2$ C. $(n - 1) / 2$ D. $n / 4$ 04. 对长度为3的顺序表进行查找，若查找第一个元素的概率为 $1 / 2$ ，查找第二个元素的概率为 $1 / 3$ ，查找第三个元素的概率为 $1 / 6$ ，则查找任意一个元素的平均查找长度为（）。 A. $5 / 3$ B. 2 C. $7 / 3$ D. $4 / 3$ 05. 下列关于二分查找的叙述中，正确的是（）。 A. 表必须有序，表可以顺序方式存储，也可以链表方式存储 B. 表必须有序且表中数据必须是整型、实型或字符型 C. 表必须有序，而且只能从小到大排列 D. 表必须有序，且表只能以顺序方式存储 <!-- page: 282 --> 2027年数据结构考研复习指导 06. 在一个顺序存储的有序线性表上查找一个数据时，既可以采用折半查找，也可以采用顺序查找，但前者比后者的查找速度（）。 A. 必然快 B. 取决于表是递增还是递减 C. 在大部分情况下要快 D. 必然不快 07. 折半查找过程所对应的判定树是一棵（）。 A. 最小生成树 B. 半衡二又树 C. 完全二又树 D. 满二又树 08. 折半查找和二又排序树的时间性能（）。 A. 相同 B. 有时不相同 C. 完全不同 D. 无法比较 09. 在有 11 个元素的有序表 $A[1,2,\dots,11]$ 中进行折半查找（$\lfloor (\log + \text{high}) / 2 \rfloor$），查找元素 $A[11]$ 时，被比较的元素下标依次是（）。 A. $6, 8, 10, 11$ B. $6, 9, 10, 11$ C. $6, 7, 9, 11$ D. $6, 8, 9, 11$ 10. 已知有序表(13, 18, 24, 35, 47, 50, 62, 83, 90, 115, 134)，当二分查找值为 90 的元素时，查找成功的元素比较次数为（）。 A. 1 B. 2 C. 4 D. 6 11. 若有序表的关键字序列为 $\{b, c, d, e, f, g, q, r, s, t\}$，则在二分查找关键字 $b$ 的过程中，进行比较的关键字依次为（）。 A. $f, c, b$ B. $f, d, b$ C. $g, c, b$ D. $g, d, b$ 12. 对表长为 $n$ 的有序表进行折半查找，其判定树的高度为（）。 A. $\left\lceil \log_2(n + 1) \right\rceil$ B. $\lfloor \log_2(n + 1) \rfloor - 1$ C. $\lceil \log_2 n \rceil$ D. $\lfloor \log_2 n \rfloor - 1$ 13. 已知一个长度为 16 的顺序表，其元素按关键字有序排列，若采用折半查找算法查找一个不存在的元素，则比较的次数至少是（），至多是（）。 A. 4 B. 5 C. 6 D. 7 14. 具有 12 个关键字的有序表中，对每个关键字的查找概率相同，折半查找算法查找成功的平均查找长度为（），折半查找查找失败的平均查找长度为（）。 A. 37/12 B. 35/12 C. 39/13 D. 49/13 15. 下列关于查找的说法中，正确的是（）。（注，涉及下节内容） A. 若数据元素保持有序，则查找时就可以采用折半查找法 B. 折半查找与二又查找树的时间性能在最坏情况下是相同的 C. 折半查找法的平均查找长度一定小于顺序查找法 D. 折半查找法查找一个元素大约需要 $O(\log_2 n)$ 次关键字比较 16. 采用分块查找时，数据的组织方式为（）。 A. 数据分成若干块，每块内数据有序 B. 数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大（或最小）的数据组成索引块 C. 数据分成若干块，每块内数据有序，每块内最大（或最小）的数据组成索引块 D. 数据分成若干块，每块（除最后一块外）中数据个数需相同 17. 对有 2500 个记录的索引顺序表（分块表）进行查找，最理想的块长为（）。 A. 50 B. 125 C. 500 D. $\lceil \log_2 2500 \rceil$ 18. 设顺序存储的某线性表共有 123 个元素，按分块查找的要求等分为 3 块。若对索引表采用顺序查找法来确定子块，且在确定的子块中也采用顺序查找法，则在等概率情况下，分块查找成功的平均查找长度为（）。 <!-- page: 283 --> 第7章 查找 271 A. 21 B. 23 C. 41 D. 62 19. 为提高查找效率，对有 65025 个元素的有序顺序表建立索引顺序结构，在最好情况下查找到表中已有元素最多需要执行（ ）次关键字比较。 A. 10 B. 14 C. 16 D. 21 20. 【2010 统考真题】已知一个长度为 16 的顺序表 $L$，其元素按关键字有序排列，若采用折半查找法查找一个 $L$ 中不存在的元素，则关键字的比较次数最多是（ ）。 A. 4 B. 5 C. 6 D. 7 21. 【2015 统考真题】下列选项中，不能构成折半查找中关键字比较序列的是（ ）。 A. 500, 200, 450, 180 B. 500, 450, 200, 180 C. 180, 500, 200, 450 D. 180, 200, 500, 450 22. 【2016 统考真题】在有 $n (n &gt; 1000)$ 个元素的升序数组 $\mathbb{A}$ 中查找关键字 $\times$。查找算法的伪代码如下所示。 ```c 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 查找失败;
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
B.
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
C.
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
D.
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
24. 【2023 统考真题】对含 600 个元素的有序顺序表进行折半查找，关键字间的比较次数最多是（ ）。
A. 9
B. 10
C. 30
D. 300
25. 【2024 统考真题】下列数据结构中，不适合直接使用折半查找的是（ ）。
I. 有序链表
II. 无序数组
III. 有序静态链表
IV. 无序静态链表
A. 仅 I, III
B. 仅 II, IV
C. 仅 II, III, IV
D. I, II, III, IV
26. 【2025 统考真题】已知查找表中有 400 个元素，查找每个元素的概率相同。采用分块查找法进行查找，且均匀分块。若采用顺序查找法确定元素所在的块，且块内也采用顺序查找法，为使查找效率最高，则每块包含的元素个数应为（ ）。
A. 8
B. 10
C. 20
D. 25
## 二、综合应用题
01. 若对有 $n$ 个元素的有序顺序表和无序顺序表进行顺序查找，试就下列三种情况分别讨论两者在相等查找概率时的平均查找长度是否相同。</n></n></n></a[k-1]="x)"></n>
<!-- page: 284 -->
2027年数据结构考研复习指导
1）查找失败。
2）查找成功，且表中只有一个关键字等于给定值 $k$ 的元素。
3）查找成功，且表中有若干关键字等于给定值 $k$ 的元素，要求一次查找能找出所有元素。
02. 有序顺序表中的元素依次为 017, 094, 154, 170, 275, 503, 509, 512, 553, 612, 677, 765, 897, 908。
1）试画出对其进行折半查找的判定树。
2）若查找275或684的元素，将依次与表中的哪些元素比较？
3）计算查找成功的平均查找长度和查找不成功的平均查找长度。
03. 已知一个有序顺序表 $A[0...8n-1]$ 的表长为 $8n$，并且表中没有关键字相同的数据元素。假设按下述方法查找一个关键字值等于给定值 $X$ 的数据元素：首先在 $A[7], A[15], A[23], \dots, A[8k-1], \dots, A[8n-1]$ 中进行顺序查找，若查找成功，则算法报告成功位置并返回；若不成功，则当 $A[8k-1] < X < A[8 \times (k+1)-1]$ 时，可确定一个缩小的查找范围 $A[8k] \sim A[8 \times (k+1)-2]$，然后可在这个范围内执行折半查找。特殊情况：若 $X > A[8n-1]$ 的关键字，则查找失败。
1）画出描述上述查找过程的判定树。
2）计算相等查找概率下查找成功的平均查找长度。
04. 写出折半查找的递归算法。初始调用时，low为1，high为ST.length。
05. 线性表中各结点的检索概率不等时，可用如下策略提高顺序检索的效率：若找到指定的结点，则将该结点和其前驱结点（若存在）交换，使得经常被检索的结点尽量位于表的前端。试设计在顺序结构和链式结构的线性表上实现上述策略的顺序检索算法。
06. 已知一个 $n$ 阶矩阵 $A$ 和一个目标值 $k$。该矩阵无重复元素，每行从左到右升序排列，每列从上到下升序排列。请设计一个在时间上尽可能高效的算法，判断矩阵中是否存在目标值 $k$。例如，矩阵为 $\begin{bmatrix} 1 & 4 & 7 \\ 2 & 5 & 8 \\ 3 & 6 & 9 \end{bmatrix}$，目标值为8，判断存在。要求：
1）给出算法的基本设计思想。
2）根据设计思想，采用C或 $C++$ 语言描述算法，关键之处给出注释。
3）说明你的算法的时间复杂度和空间复杂度。
07. 【2013 统考真题】设包含 4 个数据元素的集合 $S = \{'do', 'for', 'repeat', 'while'\}$，各元素的查找概率依次为 $p_1 = 0.35, p_2 = 0.15, p_3 = 0.15, p_4 = 0.35$。将 $S$ 保存在一个长度为 4 的顺序表中，采用折半查找法，查找成功时的平均查找长度为 2.2。
1）若采用顺序存储结构保存 $S$，且要求平均查找长度更短，则元素应如何排列？应使用何种查找方法？查找成功时的平均查找长度是多少？
2）若采用链式存储结构保存 $S$，且要求平均查找长度更短，则元素应如何排列？应使用何种查找方法？查找成功时的平均查找长度是多少？
## 7.2.5 答案与解析
### 一、单项选择题
#### 01. A
顺序查找是指从表的一端开始向另一端查找。它不要求查找表具有随机存取的特性，可以是顺序存储结构或链式存储结构。
<!-- page: 285 -->
第7章 查找
273
02. B
对于顺序查找，不管线性表是有序的还是无序的，成功查找第一个元素的比较次数为1，成功查找第二个元素的比较次数为2，以此类推，即每个元素查找成功的比较次数只与其位置有关（与是否有序无关），因此查找成功的平均时间两者相同。
03. B
在有序单链表上做顺序查找，查找成功的平均查找长度与在无序顺序表或有序顺序表上做顺序查找的平均查找长度相同，都是 $(n + 1)/2$。
04. A
在长度为3的顺序表中，查找第一个元素的查找长度为1，查找第二个元素的查找长度为2，查找第三个元素的查找长度为3，所以有
$$
\mathrm{ASL}_{\text{成功}} = \frac{1}{2} \times 1 + \frac{1}{3} \times 2 + \frac{1}{6} \times 3 = \frac{5}{3}
$$
05. D
二分查找通过下标来定位中间位置元素，所以应采用顺序存储，且二分查找能够进行的前提是查找表是有序的，但具体是从大到小还是从小到大的顺序则不做要求。
06. C
折半查找的快体现在一般情况下，在大部分情况下要快，但是对于某些特殊情况，顺序查找可能会快于折半查找。例如，查找一个含1000个元素的有序表中的第一个元素时，顺序查找的比较次数为1次，而折半查找的比较次数却将近10次。
07. B
A 显然排除。对于选项 C，考点精析示例中的判定树就不是完全二叉树。由选项 C 也可排除选项 D，且满二叉树对结点数有要求。只可能选择选项 B。事实上，由折半查找的定义不难看出，每次把一个数组从中间结点分割时，总是把数组分为结点数相差最多不超过 1 的两个子数组，从而使得对应的判定树的两棵子树高度差的绝对值不超过 1，所以应是平衡二叉树。
08. B
折半查找的性能分析可以用二叉判定树来衡量，平均查找长度和最大查找长度都是 $O(\log_2 n)$；二叉排序树的查找性能与数据的输入顺序有关，最好情况下的平均查找长度与折半查找相同，但最坏情况即形成单支树时，其查找长度为 $O(n)$。
09. B
依据折半查找算法的思想，第一次 $\mathrm{mid} = \left\lfloor (1 + 11) / 2 \right\rfloor = 6$，第二次 $\mathrm{mid} = \left\lfloor \left[ (6 + 1) + 11 \right] / 2 \right\rfloor = 9$，第三次 $\mathrm{mid} = \left\lfloor \left[ (9 + 1) + 11 \right] / 2 \right\rfloor = 10$，第四次 $\mathrm{mid} = 11$。
10. B
开始时 low 指向 13，high 指向 134，mid 指向 50，比较第一次 $90 > 50$，所以将 low 指向 62，high 指向 134，mid 指向 90，第二次比较找到 90。
11. A
在折半查找算法中，mid 取值的方式是确定的，要么采用向上取整，要么采用向下取整，而不能出现两种情况。对于选项 A，第 1 次比较的元素是 $f$，为向下取整；第 2 次比较的元素是 $c$，为向下取整；第 3 次比较的元素是 $b$，为向下取整，查找成功，符合二分查找。对于选项 B，第 1 次比较的元素是 $f$，为向下取整；第 2 次比较的元素是 $d$，为向上取整，两次 mid 取值的方式不同，不符合二分查找。对于选项 C，第 1 次比较的元素是 $g$，为向上取整；第 2 次比较的元素是 $c$，为向下取整，不符合二分查找。对于选项 D，第 1 次比较的元素是 $g$，为向上取整；第 2 次比较的元素是 $d$，为正中间元素；第 3 次比较的元素为 $b$，为向下取整，不符合二分查找。
<!-- page: 286 -->
2027年数据结构考研复习指导
12. A
对 $n$ 个结点的判定树，设结点总数 $n = 2^{h} - 1$，则 $h = \lceil \log_2(n + 1) \rceil$。
【另解】特殊值代入法。直接将 $n = 1$ 和 $n = 2$ 的情况代入，仅有 A 满足要求。
13. A、B
对于此类题，有两种做法：一种方法是，画出查找过程中构成的判定树，让最小的分支高度对应于最少的比较次数，让最大的分支高度对应于最多的比较次数，出现类似于长度为 15 的顺序表时，判定树刚好是一棵满树，此时最多比较次数与最少比较次数相等；另一种方法是，直接用公式求出最小的分支高度和最大分支高度，从前面的讲解不难看出最大分支高度为 $H = \lceil \log_2(n + 1) \rceil = 5$，这对应的就是最多比较次数，然后因为判定树不是一棵满树，所以至少应该是 4（由判定树的各分支高度最多相差 1 得出）。
注意，若求查找成功或查找失败的平均查找长度，则需要画出判定树来求解。此外，对长度为 $n$ 的有序表，采用折半查找时，查找成功和查找失败的最多比较次数相同，均为 $\lceil \log_2(n + 1) \rceil$。
14. A、D
假设有序表中元素为 A[0...11]，不难画出对它进行折半查找的判定树如下图所示，圆圈是查找成功结点，方形是虚构的查找失败结点。从而可以求出查找成功的 $\mathrm{ASL} = (1 + 2 \times 2 + 3 \times 4 + 4 \times 5) / 12 = 37 / 12$，查找失败的 $\mathrm{ASL} = (3 \times 3 + 4 \times 10) / 13$。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
注意
对于本类题目，应先根据所给 $n$ 的值，画出如上图所示的折半查找判定树。另外，查找失败结点的 ASL 不是到图中的方形结点，而是到方形结点上一层的圆形结点。
15. D
折半查找法不仅要求数据元素有序，而且要求必须为顺序存储，选项 A 错误。折半查找法在最坏情况下的时间性能为 $O(\log_2 n)$，二叉查找树在最坏情况下的时间性能为 $O(n)$，选项 B 错误。在每个元素查找概率不同的情况下，折半查找法的平均查找长度可能大于顺序查找法，选项 C 错误。
16. B
通常情况下，在分块查找的结构中，不要求每个索引块中的元素个数都相等。
17. A
设块长为 $b$，索引表包含 $n / b$ 项，索引表的 $\mathrm{ASL} = (n / b + 1) / 2$，块内的 $\mathrm{ASL} = (b + 1) / 2$，总 $\mathrm{ASL} =$ 索引表的 $\mathrm{ASL} +$ 块内的 $\mathrm{ASL} = (b + n / b + 2) / 2$，其中对于 $b + n / b$，由均值不等式可知，$b = n / b$ 时有最小值，此时 $b = \sqrt{n}$。则最理想块长为 $\sqrt{2500} = 50$。
18. B
根据公式 $\mathrm{ASL} = L_1 + L_5 = \frac{b + 1}{2} + \frac{s + 1}{2} = \frac{s^2 + 2s + n}{2s}$，其中 $b = n / s, s = 123 / 3, n = 123$，代入不难得出 ASL 为 23。所以选择选项 B。另一方面，可根据穷举法来一步步模拟。对于 A 块中的元素，查找
<!-- page: 287 -->
第7章 查找
275
过程的第一步是先找到 A 块，由于是顺序查找，找到 A 块只需一步，然后在 A 块中顺序查找，因此 A 块内各元素查找长度分别为 2, 3, 4, …, 42。对于 B 块，采用类似的方法，但查找到 B 块要比查找到 A 块多一步，因此 B 块内各元素查找长度为 3, 4, 5, …, 43。同理，C 块中各个元素查找长度为 4, 5, 6, …, 44。所以平均查找长度为 $(2 + 3 + 4 + \dots + 42 + 3 + 4 + 5 + \dots + 43 + 4 + 5 + 6 + \dots + 44) / 123 = 23$。