引言
二分查找，或许当我们遇到这个算法的时候会觉得很简单，确实如此吗？或许你也听到过，“90%以上的程序员无法正确无误的写出二分查找的代码”，反正我是听到过，无论是在《编程之美》还是《编程珠玑》抑或者网上大牛们的讨论。开始我确实也不信，但是后来发现还是不能够正确无误地完成这个代码。 正如《编程珠玑》中说的：
“二分查找可以解决（预排序数组的查找）问题：只要数组中包含 T（即要查找的值）， 那么通过不断缩小包含 T 的范围，最终就可以找到它。一开始，范围覆盖整个数组。将数 组的中间项与 T 进行比较，可以排除一半元素，范围缩小一半。就这样反复比较，反复缩 小范围，最终就会在数组中找到 T，或者确定原以为 T 所在的范围实际为空。对于包含 N 个元素的表，整个查找过程大约要经过 log(2)N 次比较。
多数程序员都觉得只要理解了上面的描述，写出代码就不难了；但事实并非如此。如果你不认同这一点，最好的办法就是放下书本，自己动手写一写。试试吧。 我在贝尔实验室和 IBM 的时候都出过这道考题。那些专业的程序员有几个小时的时间， 可以用他们选择的语言把上面的描述写出来；写出高级伪代码也可以。考试结束后，差不多所有程序员都认为自己写出了正确的程序。于是，我们花了半个钟头来看他们编写的代码经 过测试用例验证的结果。几次课，一百多人的结果相差无几：90%的程序员写的程序中有 bug（我并不认为没有 bug 的代码就正确）。 我很惊讶：在足够的时间内，只有大约 10%的专业程序员可以把这个小程序写对。但 写不对这个小程序的还不止这些人：高德纳在《计算机程序设计的艺术 第 3 卷 排序和查 找》第 6.2.1 节的“历史与参考文献”部分指出，虽然早在 1946 年就有人将二分查找的方法 公诸于世，但直到 1962 年才有人写出没有 bug 的二分查找程序。” ——乔恩·本特利，《编程珠玑（第 1 版）》第 35-36 页。
分析与解答
二分查找很多时候都可以很显著的提高查找效率，思路很简单：依据有序的条件不断的将问题解的区间缩小，直到找到最终解。但它必须满足条件：查询的序列是有序的或者是变相有序序列(例如efghabcd、4689123之类的)。因此，有时候虽然它的查找效率非常好，但是由于需要将序列先排序而降低了效率，不过在此我们只说它的查找效率，至于它的弊端我们姑且先无视。
对于二分查找的实现，我们惯常的做法是使用whie()循环，因此程序的关键部分就是初始条件、中间条件、结束条件。如果不注意的话，我们通常会写出这样的代码：
//有BUG的代码 //查找出大小等于value的值的索引 //array[]为目标数组，n为数组大小，value为目标值 //找到返回值得索引，无符合数值返回-1，可以假设无重复值 int Binary_Search(char[] array, int n, int value){ int left = 0; int right = n-1; int mid; while(left <= right){ mid = (left + right)/2; if(arrar[mid] > value) right = mid-1; else if(array[mid] < value) left = mid + 1; else return mid; } return -1; }
是不是感觉没什么错误呢？
首先是while()的条件中究竟该<=还是<的问题。如果是 int right = n 的话，那么下面循环的条件则是 while(left < right),循环内当 array[mid]>value 的时候，right = mid。如果是right = n -1的话，那么下面循环的条件则是 while(left <= right),循环内当 array[mid] >value 的时候，right = mid - 1;
此时面试官或许会说是否考虑溢出呢?即假设是在32位的机器中，如果left+right的和恰好大于2147483647，那么会造成上溢，结果会是一个负数。这个是需要避免的，怎么避免?(left+right)/2 = (2left + right - left)/2 = left + (right - left)/2，是不是可以解决呢？还有对于除以2的操作，我们还可以采用移位的方式代替，提高了运行效率，即最后是：mid = left + (right - left)>>1. 另外一个容易出错的地方是一不小心会把，mid = left + (right - left)>>1写在while()循环外面，以至于mid的值得不到更新，不要不以为意，有时候我们就是会犯这种错误。
//改正后的代码 int Binary_Search(const int array[], int n, int value){ int left = 0; int right = n - 1; while(left <= right){ //如果这里是 int right = n的话，那么下面有两处地方需要修改，以保证一一对应： //1、下面循环的条件则是 while(left < right) //2、循环内当 array[mid]>value 的时候，right = mid int mid = left + ((right-left)>>1);//防止溢出 if(array[mid] > value) right = mid - 1; else if(array[mid] < value) left = mid + 1; else return mid; } return -1; }