本章内容

• 编写第一种查找算法：二分查找
• 学习如何谈论算法的运行时间：大O表示法
• 了解一种常用的设计方法：递归

什么是算法？

• 算法是一组完成任务的指令，任何代码片段都可以视为算法。

二分查找

• 二分查找是一种算法，其输入是一个有序的元素列表(仅当列表有序的时候，二分查找才管用)。如果要查找的元素包含在列表中，二分查找返回其位置，否则返回null。

首先介绍简单查找

简单查找就是‘傻找’，例如猜测一个1~100的数字，从1开始依次往上猜，每次猜测只能排除一个数字。如果数字是99，则需要猜测99次才能猜到。

二分查找

• 而二分查找法则从50开始，一下子可以排除一半的数字；每次都猜测中间的数字，从而每次都将剩余的数字排除一半。

• 一般而言，对于包含n个元素的列表，用二分查找最多需要[latex]\log n[/latex]步，而简单查找最多需要n步。

二分查找Python代码实现

def binary_search(list, item):
    low = 0
    high = len(list) - 1 
    while low <= high: #只要范围没有缩小到只包含一个元素，就检查中间的元素
        mid = (low + high) // 2
        guess = list[mid]
        if guess == item: #找到元素了
            return mid
        if guess > item: #猜的值大了
            high = mid - 1
        else: #猜的值小了
            low = mid + 1
    return None #没有猜测的值


list = [1, 2, 3, 4, 5, 6, 7]

# 能找到对应的值
print(binary_search(list, 3))
print(binary_search(list, 6))

# 不能找到对应的值
print(binary_search(list, 8))

leetcode中的二分查找

运行时间

• 线性时间(linear time)：以简单查找为例，最多的猜测次数与列表长度相同，这被称为线性时间-O(n)。
• 对数时间(log时间):：比如二分查找-O(log n).

线性时间和对数时间的增速不同！

大O表示法

大O表示法是一种特殊的表示法，指出了算法的速度有多快，同时也表示了算法的增速的差异，其单位并不是秒，而是操作数，指出了最糟糕情况下的运行时间。

一些常见的大O运行时间

从快到慢：
O(log n) 对数时间，如二分查找
O(n) 线性时间，如简单查找
O(n * log n ) 线性对数时间，如快速排序
O([latex]n^{2}[/latex]) 平方时间，如选择排序
O(n!) 阶乘时间，如旅行商问题

小结

• 算法的速度指的并非时间，而是操作数的增速
• 谈论算法的速度时，我们说的是随着输入的增加，其运行时间将以什么样的速度增加。
• 算法的运行时间用大O表示法表示
• O(log n)比O(n)快，当需要搜索的元素越多时，前者比后者快的越多。