在公众号里写了有 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 这个元素了。
当然这就是最简单的二分法,数组中没有重复的元素,如果存在重复的元素那情况又不太一样了,后面的文章再细说。二分法虽然简单,但我还是强烈建议你亲自动手去写一写。
对了,前面有说过,二分法为啥不适合处理保存在链表中的数据,因为链表不能像数组一样通过下标快速访问元素,只能从头结点开始顺序遍历,这样效率并不是最高的。
好了,希望文章对你有一点帮助,点个在看,感谢你的支持。
推荐文章: