"二分查找可以解决（预排序数组的查找）问题：只要数组中包含T（即要查找的值），那么通过不断缩小包含T的范围，最终就可以找到它。一开始，范围覆盖整个数组。将数组的中间项与T进行比较，可以排除一半元素，范围缩小一半。就这样反复比较，反复缩小范围，最终就会在数组中找到T，或者确定原以为T所在的范围实际为空。对于包含N个元素的表，整个查找过程大约要经过log(2)N次比较。
多数程序员都觉得只要理解了上面的描述，写出代码就不难了；但事实并非如此。如果你不认同这一点，最好的办法就是放下书本，自己动手写一写。试试吧。
我在贝尔实验室和IBM的时候都出过这道考题。那些专业的程序员有几个小时的时间，可以用他们选择的语言把上面的描述写出来；写出高级伪代码也可以。考试结束后，差不多所有程序员都认为自己写出了正确的程序。于是，我们花了半个钟头来看他们编写的代码经过测试用例验证的结果。几次课，一百多人的结果相差无几：90%的程序员写的程序中有bug（我并不认为没有bug的代码就正确）。
我很惊讶：在足够的时间内，只有大约10%的专业程序员可以把这个小程序写对。但写不对这个小程序的还不止这些人：高德纳在《计算机程序设计的艺术 第3卷 排序和查找》第6.2.1节的“历史与参考文献”部分指出，虽然早在1946年就有人将二分查找的方法公诸于世，但直到1962年才有人写出没有bug的二分查找程序。 "——乔恩·本特利，《编程珠玑（第1版）》第35-36页。

于是我尝试了一下，也不能说不正确，但是确实干得不够漂亮（或者说自作聪明）。

下面是我用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;
}

三点差异

抛开语法层面的不同，有三点显著的差异。

1.while循环的判断条件不同，我的没有等于。

2.等于A[mid]判断，我放在循环外面。

3.高位改变时，我没有+1。

所有这些不同都基于一个自作聪明的想法：

标准版对于[..2,2,2...]这样有相同元素的数组，返回值是随机的，可能是相同元素中任何一个元素的位置。

于是，我为了准确的定义这种情况下，决定返回相同元素的第一个。

简单讲，标准版在对半缩小目标空间的时候，只要找到相等的元素就停止搜索了，这时候目标空间>=1。而我的版本，即使找到相等的也会接着搜索下去，直到目标空间缩小到1。

乍一看，好像我的定义更精确。然而在实际应用中，这种做法其实很愚蠢。

举例说明

白名单过滤中，假设[...lyq...]中lyq前面还有一百万个元素，标准版只要找到lyq就停止了，而我的版本为了确认这个lyq是否唯一，要把剩下的一百万个元素也搜索一遍。当你确定数组中每个元素都不同时，我这种版本简直就是没事找事干。

聪明的你，也许会问，那如果有很多个lyq怎么办？二分查找对半缩小空间也很快，貌似没什么不妥。

其实不然，就算要判断是否唯一，也很简单，根本不需要改造标准版。答案就是，对找到的元素lyq，看他前一位是否也是lyq。如果是，说明不唯一。这样做根本不用破坏核心。

感悟

经典的算法，看起来好像很简单。但是在这简单的背后，有很多边边角角的细节是被隐藏了的。活学活用，结合特定的场景扩展算法才是王道，不要总想着自己设计个新算法出来，搞个大新闻。