编程珠玑Column 4关于binary search的部分相当精彩，
1946年就有人发表binary search，但直到1962第一个正确运行的算法才写出来。尽管算法描述看起来简单明了，但是要写的正确却是有许多地方要仔细考虑。作者着重强调的是对程序正确性的分析方法，仔细分析方法的
pre-condition, invariant,和post-condition。g9老大翻译过Joshua Bloch在google blog上的文章《
号外，号外，几乎所有的binary search和mergsort都有错》，原文在
这里。今天看了下原文，有更新，对于求中值索引的c/c++方法原文仍然是有错的，本来是这样：
int
mid
=
((unsigned) (low
+
high))
>>
1
。
但是在c99标准中，对于两个signed数值之和，如果溢出结果是未定义的(undefined)，也就是说与编译器实现相关。上面的代码应该修改为：
mid
=
((unsigned
int
)low
+
(unsigned
int
)high))
>>
1
;
我查了下jdk6的java.util.Arrays的源码，joshua bloch说的这个问题已经解决，现在的binary search如下：
//
Like public version, but without range checks.
private
static
int
binarySearch0(
int
[] a,
int
fromIndex,
int
toIndex,
int
key) {
int
low
=
fromIndex;
int
high
=
toIndex
-
1
;
while
(low
<=
high) {
int
mid
=
(low
+
high)
>>>
1
;
int
midVal
=
a[mid];
if
(midVal
<
key) low
=
mid
+
1
;
else
if
(midVal
>
key) high
=
mid
-
1
;
else
return
mid;
//
key found
}
return
-
(low
+
1
);
//
key not found.
}
如原文所讨论的，采用了>>>操作符替代除以2
文章转自庄周梦蝶 ，原文发布时间2008-04-02
