Question

二分查找问题

为什么二分查找最坏时间复杂度是O(n)

Answer 1

长度为n的有序线性表，在最坏情况下，二分查找只需要比较log2n次。

一个有序线性表 可以看做在一个完全的二叉排序树
比如0 1 2 3 4 5 6 7 我们就可以看做这样一个树
4
2 6
1 3 5 7
0
二分查找在图论上的含义 正是在这样一个二叉树上查找某个节点
最多需要的比较次数也就是树的高度这么多
那么树高怎么算 就是log2(n)取整数 时间复杂度就是O(log2n)了

追问

可是我看书上说二分查找最坏时间复杂度是O(n)啊

追答

每一次查找失败，就会排除一半的数据，怎么会最坏时时间复杂度是O(n)呢？