算法图解之二分查找

什么是二分查找

首先我们通过以下假设来了解一下：

1. 假设要在电话簿中找一个名字以K打头的人，（现在谁还用电话簿！）可以从头开始翻页，直到进入以K打头的部分。但你很可能不这样做，而是从中间开始，因为你知道以K打头的名字在电话簿中间。
2. 假设你登录Facebook。当你这样做时，Facebook必须核实你是否有其网站的账户，因此必须在其数据库中查找你的用户名。如果你的用户名为karlmageddon，Facebook可从以A打头的部分开始查找，但更合乎逻辑的做法是从中间开始查找。

这是一个查找问题，在前述所有情况下，都可使用同一种算法来解决问题，这种算法就是二分查找 。二分查找是一种算法，其输入是一个有序的元素列表。如果要查找的元素包含在列表中，二分查找返回其位置；否则返回null。

工作原理

下面的示例说明了二分查找的工作原理。随便想一个1～100的数字。你的目标是以最少的次数猜到这个数字。我们跳过傻找的方式，直接进入二分查找：50》25》13》7》4》2》1。不管我心里想的是哪个数字，你在7次之内都能猜到，因为每次猜测都将排除很多数字！！一般而言，对于包含n 个元素的列表，用二分查找最多需要log2n步，而简单查找最多需要n步。

代码实现

下面来看看如何编写执行二分查找的Js代码：

1. 函数binary_search接受一个有序数组和一个元素。如果指定的元素包含在数组中，这个函数将返回其位置。你将跟踪要在其中查找的数组部分——开始时为整个数组。
2. 每次都检查中间的元素：mid = (low + high) / 2 ←—如果(low + high)不是偶数，向下取整。
3. 如果猜的数字小了，就相应地修改low：low = mid + 1。如果猜的数字大了，就修改high：high = mid - 1。

下面是具体的实现代码：