在154个元素组成有序表进行二分法查找，可能的比较次数为（）

在154个元素组成有序表进行二分法查找，可能的比较次数为（）
A：10
B：8
C：4
D：2

答案：BCD

别出新意的解题思路：

折半查找过程可用二叉树来描述，把有序表中间位置上的结点作为树的根结点，左子表和右子表分别对应树的左子树和右子树。折半查找的过程就是走一条从根节点到被查结点的一条路径，比较的次数就是该路径中结点的个数，即，该结点在树中的层数。 所以该题可以转换为求有154个结点的二叉树有几层，小于等于这个层数的数值就是答案。 又知，深度为K的二叉树最多有2的K次方-1个结点，深度为7的二叉树最多有127个结点，深度为8的二叉树最多有255个结点，所以154个结点的二叉树有8层。

代码实现：

int TestBinSearch(int first, int end)
{
if(first < end)
    {
int mid = (first + end) / 2;
int numOfLeftCmp = TestBinSearch(first, mid - 1);
int numOfRightCmp = TestBinSearch(mid + 1, end);
if(numOfLeftCmp > numOfRightCmp)
            return numOfLeftCmp + 1;
else
            return numOfRightCmp + 1;
    }
else if(first == end)
        return 1;
else
        return 0;
}
int main()
{
    cout << TestBinSearch(0, 153) << endl;
}

运行结果：
8