二分查找
二分查找是对半查找，进队列表是有序时有效。
n个元素的列表，二分查找最多需要$log_2 n$ 步，简单顺序查找最多需要n步。
对数
对数：对数运算是幂运算的逆运算
$N = a^x (a>0, a\ne1)$, $x$就是$a$为底$N$的对数，记作$x=\log_a N$,其中：
- $a$ : 底
- $N$ : 真数
- $x$ : 以$a$为底$N$的对数
幂：
log 指的都是 $\log_2$
$\log 8$ = $\log_2 8$ = 3 ($2^3 = 8$)
- 以10为底的对数称为常用对数,记为$\lg$
- 以无理数$e$($e=2.71828...$)为底的对数称为自然对数，记为$\ln$
- 零没有对数
- 实数范围内，负数没有对数；复数范围内，负数有对数
时间复杂度
简单顺序查找的实践复杂度 $O(n)$
二分查找的时间复杂度 $O( \log n)$
时间复杂度表示了最糟糕情况下的运行时间
常用时间复杂度
- $O(\log n)$ 对数时间
- $O(n)$ 线性时间
- $O(n \times \log n)$
- $O(n^2)$
- $O(n!)$ n的阶乘