折半查找有序表 (2,10,25,35,40,65,70,75,81,82,88,100)，若查找元素 75，需依次与表中元素（ ）进行比较。

A. 65,82,75 B. 70,82,75 C. 65,81,75 D. 65,81,70,75

数组查找

[tag_link]

正确答案：D

考查折半查找的查找过程。 有序表长度为 12，依据折半查找的思想：

• 第一次查找第 $\lfloor (1+12)/2\rfloor =6$ 个元素，即 65； >
• 第二次查找第 $\lfloor ((6+1)+12)/2\rfloor =9$ 个元素，即 81； >
• 第三次查找第 $\lfloor (7+(9-1))/2\rfloor =7$ 个元素，即 70； >
• 第四次查找第 $\lfloor (7+1)+8\rfloor /2=8$ 个元素，即 75。 >

比较的元素依次为 65、81、70、75。 > 对应的折半查找判定树如下图所示。 >

`        65
      /    \
    25      81
   /  \     /  \
  2    35  70   88
 /     \    \   /  \
10      40   75 82  100
`