2.3　二分查找

你小时候可能玩过这个猜数游戏：我心里想一个1和100之间的数，由你来猜。我会告诉你，你的猜测是高了还是低了。

你可能凭直觉就知道该怎么猜。你肯定不会从1开始猜，而是从正中间的50开始。为什么呢？这是因为无论是高还是低，你都能排除一半的错误选项。

如果你猜50，然后我说低了，那么你就可以猜75。这样又能从剩下的数中去掉一半。如果这次我告诉你高了，那么你就可以猜62或者63。你应该一直挑剩下数的中间值，来去掉一半选项。

我们以猜1和10之间的数为例，用下图来展示这个过程。

简单来说，这就是二分查找。

下面来看看如何将二分查找应用于有序数组。假如有序数组有9个元素。因为计算机事先不知道每一个格子的值，所以可以像下图这样表示这个数组。

假设我们想在这个有序数组中查找7。二分查找的过程如下。

第1步：从中间的格子开始查找。因为可以用数组长度除以2来计算其索引，所以可以立刻跳转到这个格子，然后检查其中的值，如下图所示。

因为值是9，所以我们知道7在它的左边。这样就排除了9右边的一半的格子（包括它自己），如下图所示。

第2步：在9左边的格子中，检查最中间的值。因为中间有两个值，所以可以随机选择其中一个，这里以左边的值为例，如下图所示。

这个值是4，7一定在它的右边。我们可以排除4及其左边的格子，如下图所示。

第3步：现在还有两个可能是7的格子。随机选择两个格子中左边的那个，如下图所示。

第4步：检查最后一个格子，如下图所示。（如果7不在那里，那么就意味着这个有序数组里没有7。）

找到7用了4步。尽管对本例来说，线性查找也需要4步，但我们马上就能见到二分查找的真正威力了。

注意，只有在有序数组中才能进行二分查找。传统数组中的值未必按顺序排列，我们无法知道到底该往左边还是右边进行查找。这就是有序数组的优势之一：可以使用二分查找。

代码实现：二分查找

以下是二分查找的Ruby实现。

def binary_search(array, search_value)
  # 首先，设定要查找的值所在位置的上下限。下限就是数组的第一个值，而上限就是最后一个值：
  lower_bound = 0
  upper_bound = array.length - 1
  # 在循环中不停检查上下限之间最中间的值：
  while lower_bound <= upper_bound do
    # 我们找到了上下限之间的中点：（因为在Ruby中整数除法的结果会向下取整，所以无须担心这个值不是整数。）
    midpoint = (upper_bound + lower_bound) / 2
    # 检查中点的值：
    value_at_midpoint = array[midpoint]
    # 如果中点的值就是要查找的值，那么查找结束。如果不是，那么就根据这个值与要查找的值的大小关系调整上下限：
    if search_value == value_at_midpoint
      return midpoint
    elsif search_value < value_at_midpoint
      upper_bound = midpoint - 1
    elsif search_value > value_at_midpoint
      lower_bound = midpoint + 1
    end
  end
  # 如果下限已经超过上限，那么就意味着要查找的值不在这个数组中：
  return nil
end

来详细分析一下这段代码。就和linear_search方法一样，binary_search方法同样以array和search_value为参数。

可以像下面这样调用这个方法。

p binary_search([3, 17, 75, 80, 202], 22)

这个方法首先会通过下面的代码设定search_value所在索引的上下限。

lower_bound = 0
upper_bound = array.length - 1

因为开始查找时，search_value可能在数组的任意位置，所以令lower_bound为第一个索引，upper_bound为最后一个索引。

查找本身位于while循环中。

while lower_bound <= upper_bound do

只要还有search_value可能存在的位置范围，这个循环就不会停止。我们马上就会看到，随着运行，这个算法会不断缩小可能范围。如果不存在可能范围，那么lower_bound <= upper_bound就不再成立，然后可以得出结论：search_value不存在于数组中。

在循环内部，以下代码会不断检查查找范围的midpoint处的值。

midpoint = (upper_bound + lower_bound) / 2
value_at_midpoint = array[midpoint]

value_at_midpoint就是查找范围中间位置的值。

如果value_at_midpoint就是要找的search_value，那么我们就“中大奖”了。这样只需返回search_value所在索引即可。

if search_value == value_at_midpoint
  return midpoint

如果search_value小于value_at_midpoint，那么就意味着search_value一定在更前面。可以让upper_bound变为midpoint左边的第一个索引，来缩小查找范围。这是因为search_value不可能在它右边。

elsif search_value < value_at_midpoint
  upper_bound = midpoint - 1

相反，如果search_value大于value_at_midpoint，那么search_value只能在midpoint的右边，因此相应地调整lower_bound。

elsif search_value > value_at_midpoint
  lower_bound = midpoint + 1

如果查找范围已经没有任何元素，那么就返回nil。在这种情况下，search_value肯定不存在于数组中。