你写的二分法可能有个bug

在公众号里写了有 80 多篇原创文章了,大家大多都是利用碎片时间来阅读公众号文章,所以我后面的文章也尽量使用更通俗、更简短的文字。

今天要聊的是二分查找法,也被称作对半查找法,是一种非常高效的查找搜索算法。使用二分查找算法有几个前提,一个就是你的数据得是有序的,如果不是有序,那就需要先排序

其实任何一种算法,都是基于某种数据结构的,二分法适用于保存在数组中的数据,像使用链表数据结构保存的数据都不适合使用二分法。

这是使用二分法的两个比较大的前提,你先知道就好了,下面再做解释。

在二分法发明之前,如果要查找某个数是否在数组中,就只能是把数组遍历一遍,然后一个一个的依次比较了,在数据量不大的情况下这么做其实也没啥问题,但是数据量达到一定的级别,或者在一些比较极端的情况下,比如数组中不存在这个数,又或者这个数存在于数组中最后一个元素,这意味着要把数组中所有的元素都遍历并且比较一遍。

我尝试了好多次用文字来解释二分法的过程,也参考了网上其他的文章,始终都觉得不容易被理解,所以我准备用一张图来描述二分法的全过程,你应该看一眼就能明白。

首先提供一个有序数组,low、mid、high 分别表示数组的起始位置、中间位置、末尾位置,注意这三个位置均为数组下标。数组一共有 11 个数字,所以刚开始时,low、mid、high 的值分别为 0、10、5,对应的元素值分别为 5、19、37。这里我们要查找的数字为 21,首先与数组中间元素 56 比较,21 比 56 要小,因为数组是有序的,那么中间元素 56 后面的元素就都不需要再看了,所以接下来把数组缩小一半,只留下 5-21 这个区间的数,然后再重复前面的步骤,不断把数组缩小,直到找到元素,或者数组缩至为空。

下面我再结合一段用 python 实现的二分算法代码,你可以对照着看。

def binarySearch(data_list, val):    
    low = 0                         # 最小数下标    
    high = len(data_list) - 1       # 最大数下标    

    while low <= high:        
        # mid = (low + high) / 2    # 这种写法会有溢出问题
        mid = low + (high-low) / 2  # 正确写法    
        if data_list[mid] == val:   # 如果中间数下标等于val, 返回            
            return mid        
        elif data_list[mid] > val:  # 如果val在中间数左边, 移动high下标            
            high = mid - 1          # 因为mid下标已经比较过了,所以减1
        else:                       # 如果val在中间数右边, 移动low下标            
            low = mid + 1           # 同样因为mid下标已经比较过了,所以加1
    return False                    # val不存在, 返回None


ret = binarySearch(list(range(20, 1000)), 76)
print(ret)

二分法的代码看起来很简单,但其实包含几个小细节,稍不注意就会掉坑里。

1、循环终止条件,是 low <= high,不能写成 low < high,不然查找数组的边界值(数组的第一个元素或最后一个元素)可能会查找失败,你自己可以去试一下。

2、mid = (low + high)/2,如果 low 和 high 都很大的情况下,可能会导致溢出问题,所以一般写成 mid = low + (high-low)/2。

3、在每次对半缩小数组后,low 和 high 移动的问题,可以看到代码里都分别有加一减一的操作,如果是直接写成 low = mid 和 high = mid 的话可能会造成死循环,我觉得死循环在这里不太好理解,你可以认为 mid 已经在上个循环中已经比较过了,所以数组折半后就不需要再比较 mid 这个元素了。

当然这就是最简单的二分法,数组中没有重复的元素,如果存在重复的元素那情况又不太一样了,后面的文章再细说。二分法虽然简单,但我还是强烈建议你亲自动手去写一写。

对了,前面有说过,二分法为啥不适合处理保存在链表中的数据,因为链表不能像数组一样通过下标快速访问元素,只能从头结点开始顺序遍历,这样效率并不是最高的。

好了,希望文章对你有一点帮助,点个在看,感谢你的支持。

推荐文章:

如何分析一条sql的性能

字符串匹配算法基础版

原文发布于微信公众号 - 谭小谭(tanstory)

原文发表时间:2019-06-21

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

扫码关注云+社区

领取腾讯云代金券