美文网首页Sunrise千日连更打卡
快速定位目标 | 二分查找算法

快速定位目标 | 二分查找算法

作者: 粽子和小恺 | 来源:发表于2021-08-26 06:28 被阅读0次

    日更进度:0005/1000天

    提示:本文章力争使普通人群理解并使用,所以不会使用任何的专业术语。


    简介

    在实际应用中,我们经常需要再一大堆数字里面寻找一个数字,并且返回它的位置。

    一个一个遍历元素吗?当然不行,如果元素数量只要几百几千个不会有什么问题。但当元素达到了千万个甚至亿个时,仅仅是遍历一遍就要很长时间,带给用户的体验自然是非常差了。

    最简单的方法自然是从中间将数组劈断,然后根据目标值与中间值选择左、右边界进行查找。

    但是,使用二分法查找的数组必须是单调的、有序的、有穷的。人脑在有序的数列里寻找一个数的时候采用的就是二分算法。


    原理

    背景
    我们现在有一组数据,为了方便,我们用一对大括号将它们括起来。既然是“一组数据”,我们就称为数组吧。我们来看看它长什么样子:

    {1,2,3,5,9,14,17,21}

    为了方便表示,我们给每个数字编一个号,第一个数字是0号,第二个是一号...以此类推,并且我们可以通过一对方括号通过给数字的编号获取这个数字。

    定义指针

    好了,现在让我们定义两个边界指针左边界 = 0,右边界 = 数组的长度 - 1(为什么要减去一呢?请在评论区留下你的答案)。现在边界定义完成了,而长度就是整个数组:

    {1,2,3,5,9,14,17,21}
    ..L.......................R【1】

    我们需要在这个数组里找到3,并返回它的编号。不急,我们先看一下它的中间是多少。

    定义中心指针,中间 = (左边 + 右边) ÷ 2【2】,然后取整。现在大家都知道,我们的中间编号是(0 + 8) ÷ 2 = 4,也就是5这个数字。

    收缩边界

    因为我们的目标是“3”,所以我们先看一下中间是几,如果是3直接返回,看一下左边界是否与右边界重合,如果是直接返回边界指针。

    我们需要寻找“3”,而中间是“5”,所以我们需要收缩右边界,我们先将其收缩至中心指针处,然后再往左收缩一格,现在边界数组变成了:

    {1,2,3,5,9,14,17,21}
    ..L...R

    注意:此时数组还是那个数组,只是寻找边界变了。

    重新计算中心指针位置为 (2 - 0) ÷ 2 = 1,数值为2。我们要寻找3,而2比3小。这时我们收缩左边界指针到中心再往右移一格。

    我们发现,这时左、右边界指针重合了,于是直接返回边界指针,查找结束。

    执行过程如下:


    算法源码如下:

    def binary_search(alist,data):
        n = len(alist)
        first = 0
        last = n-1
        while first <= last:
            mid = (first + last) // 2
            if alist[mid] < data:
                first = mid + 1
            elif alist[mid] > data:
                last = mid - 1
            else:
                return mid
        return False
    

    课后作业

    写出一个计算开平方的算法


    注解

    【1】:原数组始终不变,变化的只有寻找范围。“...”没有任何意义,只是为了美观。

    【2】:通常的开发中,为了避免巨大的加法造成溢出,通常写作左边界 + (右边界 - 左边界的形式)。

    相关文章

      网友评论

        本文标题:快速定位目标 | 二分查找算法

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