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一定在更前面?？梢宰?code>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肯定不存在于數組中。