算法解析-二分查找

常用算法学习，并附上 python 代码实现。该篇博客主要介绍二分查找算法的原理解析与代码实现。

场景解析：

       现在假设你登录 Facebook。当你这样做时，Facebook 必须核实你是否有其网站的账户，因此必须在其数据库中查找你的用户名。如果你的用户名为 karlmageddon，Facebook 可从以 A 打头的部分开始查找，但更合乎逻辑的做法是从中间开始查找。这是一个查找问题，在前述所有情况下，都可使用同一种算法来解决问题，这种算法就是二分查找 。

基本条件：

       二分查找是一种算法，其输入是一个有序的元素列表。如果要查找的元素包含在列表中，二分查找返回其位置；否则返回 null 。

算法原理解析：

       从 1-100 中随机挑出一个数字，然后用最少的次数猜中这个次数，如果用蛮力的方法从 1 开始猜，如果挑中的数字是 99 那么最起码要猜 99 次。那么介绍另外一种方法，从 50 开始猜。小了，但排除了一半的数字！至此，你知道 1 ～ 50 都小了。接下来，你猜 75。大了，那余下的数字又排除了一半！使用二分查找时，你猜测的是中间的数字，从而每次都将余下的数字排除一半。接下来，你猜 63（50 和 75 中间的数字）。经过几次猜测即可猜中。这就是二分查找原理。那么对于二分查找一般多少次可以能猜中呢。

答案：log₂N 次

公式解析：对数

       你可能不记得什么是对数了，但很可能记得什么是幂。log₁₀ 100 相当于问“将多少个 10 相乘的结果为 100”。答案是两个：10 × 10 = 100。因此，log₁₀ 100 = 2。对数运算是幂运算的逆运算。

code 片段演示：

# -*- coding: utf-8 -*-

"""二分查找代码实现"""


def fastSearch(glist, guess):
    start = 0
    end = len(glist) - 1
    while start <= end:
        mid = (end + start) // 2
        if guess == glist[mid]:
            return mid
        elif guess > glist[mid]:
            start = mid + 1
        else:
            end = mid - 1
    return None


if __name__ == "__main__":
    ls = [1, 2, 3, 4, 5, 6, 7, 8]
    guess = 3
    print(fastSearch(ls, guess))

注意事项：

数组一定是有序的。

运行时间:

一般而言，应选择效率最高的算法，以最大限度地减少运行时间或占用空间。对于 40 亿有序数组的普通查找最多用 40 亿次方可查询到，对于查询时间与数组长度成正比，称为线性时间。而对于通过二分法查找的方式，40 亿数组则需要最多需要 40 亿的对数次。二分查找的运行时间为对数时间。

大 O 表示法:

大 O 表示法是一种特殊方法，他表示方法的速度有多快。表示方法是 O(log₂N).其中 log₂N 表示操作数。

适用场景:

大 O 表示法所能代表的是当前算法最糟糕的时候运行时间。

常见运行时间:

1. O(logn)，也叫对数时间，这样的算法包括二分查找。
2. O(n)，也叫线性时间，这样的算法包括简单查找。
3. O(n*logn)，这样的算法包括第 4 章将介绍的快速排序——一种速度较快的排序算法。
4. O(n2)，这样的算法包括第 2 章将介绍的选择排序——一种速度较慢的排序算法。
5. O(n!)，这样的算法包括接下来将介绍的旅行商问题的解决方案——一种非常慢的算法。

运行时间总结:

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