题20

题20

题目

【2010 统考真题】已知一个长度为 16 的顺序表 ,其元素按关键字有序排列，若采用折半查找法查找一个 中不存在的元素，则关键字的比较次数最多是 ( ).
A. 4
B. 5
C. 6
D. 7

分析

和解是一样的，考察折半查找的判定树最大分支高度为

解

B
折半查找法在查找不成功时和给定值进行关键字的比较次数最多为树的高度,即 或 。在本题中, ,所以比较次数最多为 5 。
注意，在折半查找判定树中的方形结点是虚构的, 它不计入比较的次数。

[!CITE]-
好的，我们来详细解释一下折半查找判定树中的“方形节点”，以及它们的意义。

什么是方形节点？

在折半查找的判定树中，我们通常用两种形状的节点来表示不同的含义：

• 圆形节点（或椭圆节点）： 代表实际参与比较的元素，也就是数组中真实存在的元素。
• 方形节点： 代表虚构的、查找失败的情况，也就是当目标值不在数组中时，最终会到达的节点。

为什么要有方形节点？

方形节点的存在，主要是为了完整地描述所有可能的查找路径，包括查找成功和查找失败的情况。

1. 模拟查找失败的情况： 当目标值不在数组中时，折半查找会不断缩小范围，最终会到达一个范围为空的情况。方形节点就是用来表示这种范围为空的“虚构”位置。
2. 保持树的完整性： 为了让判定树成为一个完整的二叉树，即使在目标值不存在的情况下，也需要有对应的叶子节点来表示查找的终点。
3. 便于计算查找效率： 有了方形节点，我们可以更准确地计算平均查找长度（ASL），包括查找成功和失败两种情况的查找次数。

具体例子说明：

假设有一个有序数组 [1, 2, 3, 4, 5, 6, 7]。

• 圆形节点： 1, 2, 3, 4, 5, 6, 7 这些数字在数组中实际存在，它们在判定树中用圆形节点表示。
• 方形节点：
  • 如果我们要查找 0，在经过一系列比较后，会到达一个“虚构”的位置，这个位置在 1 的左边。
  • 如果我们要查找 8，在经过一系列比较后，会到达一个“虚构”的位置，这个位置在 7 的右边。
  • 如果我们要查找 3.5，在经过一系列比较后，会到达一个“虚构”的位置，这个位置在 3 和 4 之间。
  • 这些虚构的位置在判定树中用方形节点表示。

为什么方形节点不计入比较次数？

1. 不是真实的比较： 方形节点代表查找失败的情况，也就是说，我们并没有真正用目标值去和数组中的某个值进行比较。
2. 代表查找结束： 当我们到达方形节点时，表示折半查找已经结束，因为我们已经确定目标值不存在。
3. 计算查找长度： 在计算平均查找长度时，我们只统计实际进行的比较次数，也就是到达圆形节点的路径长度。方形节点只是为了表示查找失败的路径，不参与比较次数的计算。

总结一下：

• 方形节点是虚构的： 它们代表查找失败的情况，并不对应数组中实际的元素。
• 方形节点是必要的： 它们帮助我们完整地描述折半查找的所有可能的路径。
• 方形节点不计入比较次数： 因为到达方形节点时，实际的比较过程已经结束。

你可以把方形节点想象成一个“路牌”，它告诉你“这里没你要找的东西，到头了”。虽然它也是判定树的一部分，但它本身并不参与查找的比较过程。