快速定位目标 | 二分查找算法
日更进度: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】:通常的开发中,为了避免巨大的加法造成溢出,通常写作左边界 + (右边界 - 左边界的形式)。