用递归算法实现n个相异元素构成的有序序列的二分查找,采用一个递归工作栈时,该栈的最小容量应为_

Question

用递归算法实现n个相异元素构成的有序序列的二分查找，采用一个递归工作栈时，该栈的最小容量应为______。

A．n

B．n/2

C．log2n

D．log2(n+1)

Answer 1

正确答案：D
解析：二分查找亦称折半查找，其基本思想：设查找表的元素存储在一维数组r[1..n]中，首先将待查的key值与表r中间位置上(下标为mid)的记录的关键字进行比较，若相等，则查找成功：若key＞r[mid]．key，则说明待查记录只可能在后半个子表r[mid+1..n](注意：是mid+1，而不是mid)中，下一步应在后半个子表中再进行折半查找，若keyr[mid].key，则说明待查记录只可能在前半个子表r[1..mid-1](注意：是mid-1，而不是mid)中，下一步应在前半个子表中再进行折半查找，这样通过逐步缩小范围，直到查找成功或予表为空时失败为止。
  在表中的元素已经按关键字递增(或递减)的方式排序的情况下，才可进行折半查找。
  等概率情况下顺序查找成功的平均查找长度为：当n值较大时，ASLbs≈log₂(n+1)-1。