对有14个数据元素的有序表R[14]进行折半搜索,搜索到R[3]的关键码等于给定值,此时元素比较顺序依

Question

对有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]

Answer 1

正确答案：C
解析：折半查找是一种效率较高的查找方法，要求线性表是有序表。基本思想是：首先将待查的x值和有序表R[0]到R[n-1]的中间位置mid上的节点的关键字进行比较，若相等，则查找完成；否则，若R[mid].key＞K，则说明待查找的节点只可能在左子表R[0]到R[mid-1]中，我们只要在左子表中继续进行折半查找，若R[mid].keyK，则说明待查找的节点只可能在右子表R[mid+1]到R[n-1]中，我们只要在右子表中继续进行折半查找。这样，经过一次关键字比较就缩小一半的查找空间。如此进行下去，直到找到关键字为K的节点，或者当前的查找区间为空(表示查找失败)。根据这个思想，查找的顺序即为R[6]，R[2]，R[4]，R[3]。