长度为n的有序线性表，在最坏情况下，二分查找只需要比较log2n次。
一个有序线性表 可以看做在一个完全的二叉排序树
比如0 1 2 3 4 5 6 7 我们就可以看做这样一个树
4
2 6
1 3 5 7
0
二分查找在图论上的含义 正是在这样一个二叉树上查找某个节点
最多需要的比较次数也就是树的高度这么多
那么树高怎么算 就是log2(n)取整数 时间复杂度就是O(log2n)了
内容全部来源于网络收集，如有侵权，请联系网站删除：QQ：24596024