"二分查找可以解决（预排序数组的查找）问题：只要数组中包含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。如果是，说明不唯一。这样做根本不用破坏核心。
感悟
经典的算法，看起来好像很简单。但是在这简单的背后，有很多边边角角的细节是被隐藏了的。活学活用，结合特定的场景扩展算法才是王道，不要总想着自己设计个新算法出来，搞个大新闻。
