对长度为n的有序表二分查找，则对所有元素的最长查找长度为

Question

2．对长度为n的有序表二分查找，则对所有元素的最长查找长度为( )。
A.log2(n+1) B. log2n C. n/2 D. (n+1)/2
对有n个记录的有序表采用二分查找，其平均查找长度的量级为( )。
A O(n) B O(n2) C O(1) D O(log2n)
最长和平均的查找长度是

Answer 1

A. log2(n+1)。因为在最坏情况下，二分查找需要将表分成长度为1的子表，而长度为1的子表只需要1次比较就可以确定元素位置，所以最长查找长度为将表分成长度为1的子表的次数，即将长度为n的表分成长度为1的子表需要进行log2(n+1)次划分。

D. O(log2n)。二分查找的平均查找长度为O(log2n)。因为每次查找可以将查找区间缩小一半，所以最多需要进行log2n次查找就可以找到目标元素，因此平均查找长度为O(log2n)。