浅谈二分查找

二分查找是一种算法，其输入是一个有序的元素列表（必须有序的原因稍后解释）。如果要查找的元素包含在列表中，二分查找返回其位置；否则返回null 。

1. 下面是一个例子：

我随便想一个 1～100 的数字，你的目标是以最少的次数猜到这个数字。你每次猜测后，我会说小了、大了或对了。假设你从 1 开始依次往上猜，每次猜测都只能排除一个数字。如果我想的数字是 99，你得猜 99 次才能猜到！

更佳的查找方式（二分查找）

我们直接上代码

func binarySearch(list: [Int], item: Int) -> Int? {
    var low = 0
    var high = list.count - 1
    while low <= high {
        let mid = (low + high) / 2
        let guess = list[mid]
        if guess == item { return mid }
        if guess > item {
            high = mid - 1
        } else {
            low = mid + 1
        }
    }
    return nil
}

let myList = [1, 3, 5, 7, 9]
let result = binarySearch(list: myList, item: 7) // result is 3

2. 运行时间

每次介绍算法时，我都将讨论其运行时间。一般而言，应选择效率最高的算法，以最大限度地减少运行时间或占用空间。回到前面的二分查找。使用它可节省多少时间呢？简单查找逐个地检查数字，如果列表包含 100 个数字，最多需要猜 100 次。如果列表包含 40 亿个数字，最多需要猜 40 亿次。换言之，最多需要猜测的次数与列表长度相同，这被称为线性时间(linear time)。
二分查找则不同。如果列表包含 100 个元素，最多要猜 7 次；如果列表包含 40 亿个数字，最多需猜 32 次。厉害吧？二分查找的运行时间为对数时间(或log时间)。

3. 大O表示法

大O表示法指出了算法有多快。例如，假设列表包含 n 个元素。简单查找需要检查每个元素，因此需要执行 n 次操作。使用大O 表示法，这个运行时间为 O (n )。单位秒呢？没有—— 大O 表示法指的并非以秒为单位的速度。
大O 表示法让你能够比较操作数，它指出了算法运行时间的增速。

3.1 大O表示法让你能够比较操作数，它指出了算法运行时间的增速

下面按从快到慢的顺序列出了你经常会遇到的 5 种大O 运行时间。

O (log n )，也叫对数时间，这样的算法包括二分查找。
O (n )，也叫线性时间，这样的算法包括简单查找。
O (n * log n )，这样的算法包括快速排序(一种速度较快的排序算法)。
O (n 2 )，这样的算法包括选择排序(一种速度较慢的排序算法)。
O (n !)，这样的算法包括旅行商问题的解决方案(一种非常慢的算法)

4. 小结

二分查找的速度比简单查找快得多
O (log n ) 比 O (n ) 快。需要搜索的元素越多，前者比后者就快得越多。
算法运行时间并不以秒为单位。
算法运行时间是从其增速的角度度量的。
算法运行时间用大O 表示法表示。