美文网首页程序员
猜数字游戏--二分查找显威力

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

作者: juste | 来源:发表于2019-03-29 17:02 被阅读4次

    写在前面


    突然发现一本很有趣的算法书,打算把许久没看的算法捡一下,在进行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))
    

    运行结果如下:


    相关文章

      网友评论

        本文标题:猜数字游戏--二分查找显威力

        本文链接:https://www.haomeiwen.com/subject/dshrbqtx.html