问题
单项选择题
对有14个数据元素的有序表R[14]进行折半搜索，搜索到R[3]的关键码等于给定值，此时元素比较顺序依次为
A．R[0]，R[1]，R[2]，R[3]
B．R[0]，R[13]，R[2]，R[3]
C．R[6]，R[2]，R[4]，R[3]
D．R[6]，R[4]，R[2]，R[3]
答案
参考答案：C
解析： 折半查找是一种效率较高的查找方法，要求线性表是有序表。基本思想是：首先将待查的K值和有序表R[0]到R[n-1]的中间位置mid上的结点的关键字进行比较，若相等，则查找完成；否则，若R[mid].key＞K，则说明待查找的结点只可能在左子表R[0]到R[mid-1]中，我们只要在左子表中继续进行折半查找，若R[mid].key＜K，则说明待查找的结点只可能在右子表R[mid+1]到R[n-1]中，我们只要在右子表中继续进行折半查找。这样，经过一次关键字比较就缩小一半的查找空间。如此进行下去，直到找到关键字为K的结点，或者当前的查找区间为空 (表示查找失败)。根据这个思想，查找的顺序即为R [6]，R[2]，R[4]，R[3]。