日更进度：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】：通常的开发中，为了避免巨大的加法造成溢出，通常写作左边界 + (右边界 - 左边界的形式)。
网友评论