二分法的时间复杂度为O（log2n）是什么意思

Question

如题所述

Answer 1

网页链接

你可以看看我的上面这个博客

由于二分查找每次查询都是从数组中间切开查询，所以每次查询，剩余的查询数为上一次的一半，从下表可以清晰的看出查询次数与剩余元素数量对应关系

表-查询次数及剩余数

第几次查询    剩余待查询元素数量    

1                    N/2    

2                    N/(2^2)    

3                    N/(2^3)    

…                    …    

K                    N/(2^K)    

从上表可以看出N/(2^K)肯定是大于等于1，也就是N/(2^K)>=1，我们计算时间复杂度是按照最坏的情况进行计算，也就是是查到剩余最后一个数才查到我们想要的数据，也就是 
N/(2^K)=1 
=>N=2^K 
=>K=log2N 
所以二分查找的时间复杂度为O(log2N)

Answer 2

二分查找基本思路是先确定该区间的中间点,然后比较,再一半中再找中间点比较……直到找到.设中间点总数：n,平均查找长度为(n+1)∕ n×㏒2﹙n＋1﹚ －1 ≈㏒2﹙n＋1﹚－1
在应用极限化简就是log2(n)