"二分查找可以解決（預(yù)排序數(shù)組的查找）問題：只要數(shù)組中包含T（即要查找的值），那么通過不斷縮小包含T的范圍，最終就可以找到它。一開始，范圍覆蓋整個(gè)數(shù)組。將數(shù)組的中間項(xiàng)與T進(jìn)行比較，可以排除一半元素，范圍縮小一半。就這樣反復(fù)比較，反復(fù)縮小范圍，最終就會(huì)在數(shù)組中找到T，或者確定原以為T所在的范圍實(shí)際為空。對于包含N個(gè)元素的表，整個(gè)查找過程大約要經(jīng)過log(2)N次比較。
多數(shù)程序員都覺得只要理解了上面的描述，寫出代碼就不難了；但事實(shí)并非如此。如果你不認(rèn)同這一點(diǎn)，最好的辦法就是放下書本，自己動(dòng)手寫一寫。試試吧。
我在貝爾實(shí)驗(yàn)室和IBM的時(shí)候都出過這道考題。那些專業(yè)的程序員有幾個(gè)小時(shí)的時(shí)間，可以用他們選擇的語言把上面的描述寫出來；寫出高級偽代碼也可以。考試結(jié)束后，差不多所有程序員都認(rèn)為自己寫出了正確的程序。于是，我們花了半個(gè)鐘頭來看他們編寫的代碼經(jīng)過測試用例驗(yàn)證的結(jié)果。幾次課，一百多人的結(jié)果相差無幾：90%的程序員寫的程序中有bug（我并不認(rèn)為沒有bug的代碼就正確）。
我很驚訝：在足夠的時(shí)間內(nèi)，只有大約10%的專業(yè)程序員可以把這個(gè)小程序?qū)憣?。但寫不對這個(gè)小程序的還不止這些人：高德納在《計(jì)算機(jī)程序設(shè)計(jì)的藝術(shù) 第3卷 排序和查找》第6.2.1節(jié)的“歷史與參考文獻(xiàn)”部分指出，雖然早在1946年就有人將二分查找的方法公諸于世，但直到1962年才有人寫出沒有bug的二分查找程序。 "——喬恩·本特利，《編程珠璣（第1版）》第35-36頁。

于是我嘗試了一下，也不能說不正確，但是確實(shí)干得不夠漂亮（或者說自作聰明）。

下面是我用Ruby寫的：

  class Array
  # Ord a -> [a] -> a -> Maybe Int
  def ibsearch(x)
    return nil if self.empty?
    low, heigh = 0, self.length - 1
    while low < heigh
        mid = (low + heigh) / 2
        x <= self[mid]? heigh = mid : low = mid + 1
    end
    x == self[low]? low : nil
  end
end

這是測試用例：

class TestBsearch < Test::Unit::TestCase
  def test_bsearch
    count = 100
    count.times do
      xs = Array.new(SecureRandom.random_number(count))
      xs.map! { |e| SecureRandom.random_number(count) }
      xs.sort!
      x = xs.sample
      index = xs.index(x)
      assert_equal(index,xs.ibsearch(x))
    end
  end

  def test_bsearch_not_exit
    count = 100
    count.times do
      xs = Array.new(SecureRandom.random_number(count))
      xs.map! { |e| SecureRandom.random_number(count) }
      xs.sort!
      x = count + 1
      assert_equal(nil,xs.ibsearch(x))
    end
  end
end

測試都能通過，聰明的你，能看出哪里不夠漂亮么？

下面是維基百科上的C/C++寫的：

int binary_search(int A[], int key, int imin, int imax)
{
  // continue searching while [imin,imax] is not empty
  while (imin <= imax)
    {
      // calculate the midpoint for roughly equal partition
      int imid = midpoint(imin, imax);
      if(A[imid] == key)
        // key found at index imid
        return imid;
      // determine which subarray to search
      else if (A[imid] < key)
        // change min index to search upper subarray
        imin = imid + 1;
      else         
        // change max index to search lower subarray
        imax = imid - 1;
    }
  // key was not found
  return KEY_NOT_FOUND;
}

三點(diǎn)差異

拋開語法層面的不同，有三點(diǎn)顯著的差異。

1.while循環(huán)的判斷條件不同，我的沒有等于。

2.等于A[mid]判斷，我放在循環(huán)外面。

3.高位改變時(shí)，我沒有+1。

所有這些不同都基于一個(gè)自作聰明的想法：

標(biāo)準(zhǔn)版對于[..2,2,2...]這樣有相同元素的數(shù)組，返回值是隨機(jī)的，可能是相同元素中任何一個(gè)元素的位置。

于是，我為了準(zhǔn)確的定義這種情況下，決定返回相同元素的第一個(gè)。

簡單講，標(biāo)準(zhǔn)版在對半縮小目標(biāo)空間的時(shí)候，只要找到相等的元素就停止搜索了，這時(shí)候目標(biāo)空間>=1。而我的版本，即使找到相等的也會(huì)接著搜索下去，直到目標(biāo)空間縮小到1。

乍一看，好像我的定義更精確。然而在實(shí)際應(yīng)用中，這種做法其實(shí)很愚蠢。

舉例說明

白名單過濾中，假設(shè)[...lyq...]中l(wèi)yq前面還有一百萬個(gè)元素，標(biāo)準(zhǔn)版只要找到lyq就停止了，而我的版本為了確認(rèn)這個(gè)lyq是否唯一，要把剩下的一百萬個(gè)元素也搜索一遍。當(dāng)你確定數(shù)組中每個(gè)元素都不同時(shí)，我這種版本簡直就是沒事找事干。

聰明的你，也許會(huì)問，那如果有很多個(gè)lyq怎么辦？二分查找對半縮小空間也很快，貌似沒什么不妥。

其實(shí)不然，就算要判斷是否唯一，也很簡單，根本不需要改造標(biāo)準(zhǔn)版。答案就是，對找到的元素lyq，看他前一位是否也是lyq。如果是，說明不唯一。這樣做根本不用破壞核心。

感悟

經(jīng)典的算法，看起來好像很簡單。但是在這簡單的背后，有很多邊邊角角的細(xì)節(jié)是被隱藏了的?；顚W(xué)活用，結(jié)合特定的場景擴(kuò)展算法才是王道，不要總想著自己設(shè)計(jì)個(gè)新算法出來，搞個(gè)大新聞。