折半查找(二分查找)要求查找表必须()。A. 有序且采用顺序存储B. 无序但采用顺序存储C. 任意存储结构均可D. 有序且采用链式存储

本题考查折半查找（二分查找）对查找表的要求，解题思路是明确折半查找的原理，根据原理分析查找表需要满足的条件。

折半查找的基本原理是：在有序表中，取中间记录作为比较对象，若给定值与中间记录的关键字相等，则查找成功；若给定值小于中间记录的关键字，则在中间记录的左半区继续查找；若给定值大于中间记录的关键字，则在中间记录的右半区继续查找。不断重复上述过程，直到查找成功，或所查找的区域无记录，查找失败。

1. 分析查找表必须有序

从折半查找的原理可知，每次比较后都要根据比较结果确定下一步查找的区间是左半区还是右半区。如果查找表无序，就无法根据中间元素与目标元素的大小关系来缩小查找范围，也就不能使用折半查找。所以查找表必须是有序的。

2. 分析查找表必须采用顺序存储

折半查找需要能够快速定位中间元素，在顺序存储结构中，可以通过数组下标直接计算中间元素的位置。假设数组为 $arr$，长度为 $n$，初始查找区间的左右边界分别为 $left = 0$ 和 $right = n - 1$，则中间元素的下标 $mid$ 可以通过公式 $mid=\lfloor\frac{left + right}{2}\rfloor$ 计算得到，这样就能在 $O(1)$ 时间复杂度内定位到中间元素。

而在链式存储结构中，要访问中间元素，需要从头节点开始依次遍历，时间复杂度为 $O(n)$，这就失去了折半查找每次查找能将查找区间缩小一半的优势，所以折半查找要求查找表采用顺序存储。

综上，折半查找要求查找表必须有序且采用顺序存储。