猜数字游戏--二分查找显威力

2019-03-29 本文已影响4人 juste

写在前面

突然发现一本很有趣的算法书，打算把许久没看的算法捡一下，在进行Flask框架的学习之前，下定决心要好好地写blog，记录自己的总结和反思。本机环境Ubuntu18.04，所用编辑器为Remarkable，不过在今天早上最后插公式，软件崩溃后没有保存记录，又得重新构思一遍，现在用Atom替换了它。下面向大家推荐一下数据结构和算法的书籍，数据结构推荐封老师的《大话数据结构》使用C语言实现、算法则推荐自己看第二遍的《算法图解》，使用Python实现。下面让我们走进第一篇，二分查找那不为人知的内心世界。

猜数字游戏

小时候老师让我们做过这么一个趣味游戏：猜数字，他给出了一个1到100之间的数字，然后让全班同学猜，游戏规则是这样的：要是同学猜的数字大了，老师会给出提示：猜大了，同理小的老师也会给出提示，要是正确老师会给出猜对了。一节课就在这么一顿乱猜中结束了，大家都是乱猜，偶尔会瞎猫碰到死耗子，然后结束的时候老师告诉我们，你们可以每次猜中间的数字，这样就可以很快的猜出结果了，之后看到类似的问题，就很快能想到这种方法，但百思不得姐（好吧，其实我没思过）。直到了解了算法才知道为什么需要这么猜，下面让我们进行画面重现。

梦回幼儿园

规则就像刚才说的一样，现在开始猜数字，假设待猜数字为57，让我们先用之前的猜法试一下，一个一个猜，从1开始，这样猜的话，最少得猜57次，6要是99的话，得猜99次，现在让我们试一下从中间开始的猜法。从50开始，则猜数过程如下:
50---->小了、75---->大了、63---->大了、57---->猜对了
从以上过程可以看出，从中间查找，要比一个一个按顺序查找快很多，随着数据规模的增大，这种差异会越来越明显。（感兴趣的话可以自己试一下吧！）下面让我们热烈欢迎今天的主角，二分查找算法。

二分查找算法

猜数字的时候，有个隐含的前提，它给出了一个猜的范围，我们也发现这些序列是连续的，其实从中间开始猜数字就蕴含了二分查找的思想，或者说它就是通过二分查找来实现的，每次排除一半错误的答案，来逼近正确答案，跟学过的对数函数一样
分析之前得了解时间复杂度、空间复杂度及大O表示法，这几个概念，在此假设大家都熟悉这几个知识点（我差不多都忘完了），在此先给出一些常见的大O运行时间（由快到慢排布）：

$O (log n )$ ,也叫对数时间 ,这样的算法包括二分查找。
$O (n )$ ,也叫线性时间 ,这样的算法包括简单查找。
$O (n * log n )$ ,这样的算法包括快速排序——一种速度较快的排序算法。
$O(n^2)$ ,这样的算法包括选择排序——一种速度较慢的排序算法。
$O(n!)$ ,这样的算法包括旅行商问题的解决方案——一种非常慢的算法。
下面给出代码实现：

def binary_search(list, item):
    low = 0  # 查找范围下限
    high = len(list) - 1  # 查找范围上限
    # print(high)
    while(low <= high):
        mid = (low + high) // 2  # 下标需为整数
        guess = list[mid]  # 从中间得到所猜的数
        # print(guess)
        if(guess == item):  # 刚好猜准
            return(mid)  # 跳出并返回下标
        elif(guess < item):  # 猜的数字小了，则小于中间数的那一半均小于所猜数
            low = mid+1
        else:  # # 猜的数字大了，则大于中间数的那一半均大于所猜数
            high = mid - 1
    return(None)

# 测试用例
sea_num = int(input("请输入一个0-10的测试数字，查找不到则返回None:"))
list1 = [2, 4, 5, 6, 9, 10]
print(binary_search(list1, sea_num)）

运行结果如下：

猜数字游戏--二分查找显威力

写在前面