若有18个元素的有序表存放在一维数组A[19]中,第一个元素放A[1]中,现进行二分查找,则查找A[3]的比较序列的下标依次为( )。A. 1,2,3B. 9,5,2,3C. 9,5,3D. 9,4,2,3

考查要点：本题主要考查二分查找算法的实现细节，特别是中间位置计算和查找区间调整的逻辑。

解题核心思路：

1. 明确数组索引范围：数组从A[1]到A[18]共18个元素。
2. 二分查找的核心步骤：每次取中间位置mid，比较目标值与中间元素，调整low或high缩小搜索范围。
3. 关键细节：中间位置mid的计算方式为(low + high) // 2（向下取整），并根据比较结果动态调整区间。

破题关键点：

• 初始区间：low = 1，high = 18。
• 每次比较后，若中间元素大于目标值，则high = mid - 1；若小于，则low = mid + 1。
• 终止条件：当low > high或找到目标值。

二分查找过程模拟

1. 第一次比较：

   • 初始区间：low = 1，high = 18。
   • 计算中间位置：mid = (1 + 18) // 2 = 9。
   • 比较A[9]与目标A[3]。若A[9] > A[3]，则调整区间为low = 1，high = 8。

2. 第二次比较：

   • 新区间：low = 1，high = 8。
   • 计算中间位置：mid = (1 + 8) // 2 = 4。
   • 比较A[4]与目标A[3]。若A[4] > A[3]，则调整区间为low = 1，high = 3。

3. 第三次比较：

   • 新区间：low = 1，high = 3。
   • 计算中间位置：mid = (1 + 3) // 2 = 2。
   • 比较A[2]与目标A[3]。若A[2] < A[3]，则调整区间为low = 3，high = 3。

4. 第四次比较：

   • 新区间：low = 3，high = 3。
   • 计算中间位置：mid = (3 + 3) // 2 = 3。
   • 比较A[3]与目标A[3]，匹配成功。

比较序列：9 → 4 → 2 → 3，对应选项D。