问题介绍

为什么二分查找的复杂度是$O(lo{g}_{2}n)$

1. 考虑整个序列的长度是N，每一次查找都会把要查找的长度缩短一半。
2. 最后，当序列的长度为1的时候，就查找结束了。

设查找的次数为

m

m

m

N

2

m

=

1

\frac{N}{2^m} =1

2mN​=1

N

=

2

m

N = 2^m

N=2m

m

=

l

o

g

2

N

m = log_2 N

m=log2​N
所以就可以得到二分查找的复杂度是

O

(

l

o

g

2

n

)

O(log_2 n)

O(log2​n)
今天想到了这个问题，记录一下。