图解二分查找算法

算法是一组完成任务的指令,任何代码片段都可视为算法。本文主要描述一下二分查找算法。

假设要在电话簿中找一个名字以K打头的人,可以从头开始翻页,直到进入以K打头的部分。但你很可能不这样做,而是从中间开始,因为你知道以K打头的名字在电话簿中间。又假设要在字典中找一个以O打头的单词,你也将从中间附近开始。

现在假设你登录Facebook。当你这样做时,Facebook必须核实你是否有其网站的账户,因此必须在其数据库中查找你的用户名。如果你的用户名为karlmageddon,Facebook可从以A打头的部分开始查找,但更合乎逻辑的做法是从中间开始查找。

这是一个查找问题,在前述所有情况下,都可使用同一种算法来解决问题,这种算法就是二分查找。

二分查找是一种算法,其输入是一个有序的元素列表(必须有序的原因稍后解释)。如果要 查找的元素包含在列表中,二分查找返回其位置;否则返回null。
下图是一个例子:

图片.png

下面的示例说明了二分查找的工作原理。我随便想一个1~100的数字:
图片.png

你的目标是以最少的次数猜到这个数字。你每次猜测后,我会说小了、大了或对了。假设你从1开始依次往上猜,猜测的过程会是这样:
图片.png
这是简单查找,更准确的说法是傻找。每次猜测都只能排除一个数字。如果我想的数字是99,你得猜99次才能猜到!


更佳的查找方式

下面是一种更佳的猜法。从50开始。

图片.png

小了,但排除了一半的数字!至此,你知道1~50都小了。接下来,你猜75:

图片.png

大了,那余下的数字又排除了一半!使用二分查找时,你猜测的是中间的数字,从而每次都将余下的数字排除一半。接下来,你猜63(50和75中间的数字)。
图片.png

这就是二分查找,你学习了第一种算法!每次猜测排除的数字个数如下:

图片.png

不管我心里想的是哪个数字,你在7次之内都能猜到,因为每次猜测都将排除很多数字!假设你要在字典中查找一个单词,而该字典包含240000个单词,你认为每种查找最多需要多少步?如果要查找的单词位于字典末尾,使用简单查找将需要240000步。使用二分查找时,每次排除一半单词,直到最后只剩下一个单词。

图片.png

因此,使用二分查找只需18步——少多了!一般而言,对于包含n个元素的列表,用二分查找最多需要log2n步,而简单查找最多需要n步。

对数

你可能不记得什么是对数了,但很可能记得什么是幂。log10100相当于问“将多少个10相乘的结果为100”。答案是两个:10 × 10 = 100。因此,log10100 = 2。对数运算是幂运算的逆运算:

图片.png

下面来看看如何编写执行二分查找的Python代码。函数binary_search接受一个有序数组和一个元素。如果指定的元素包含在数组中,这个函数将返回其位置。你将跟踪要在其中查找的数组部分——开始时为整个数组:
图片.png

你每次都检查中间的元素:
图片.png

如果猜的数字小了,就相应地修改low:

图片.png

如果猜的数字大了,就修改high。完整的代码如下:

图片.png

运行时间

每次介绍算法时,我都将讨论其运行时间。一般而言,应选择效率最高的算法,以最大限度地减少运行时间或占用空间。

回到前面的二分查找。使用它可节省多少时间呢?简单查找逐个地检查数字,如果列表包含100个数字,最多需要猜100次。如果列表包含40亿个数字,最多需要猜40亿次。换言之,最多需要猜测的次数与列表长度相同,这被称为线性时间(lineartime)。

二分查找则不同。如果列表包含100个元素,最多要猜7次;如果列表包含40亿个数字,最多需猜32次。厉害吧?二分查找的运行时间为对数时间(或log时间)。下图(查找算法的运行时间)总结了我们发现的情况:

图片.png