折半查找
折半查找（二分查找）是一种简单而又高效的查找算法，其查找长度至多为㏒2n+1（判定树的深度），平均查找长度为㏒2(n+1)-1，效率比顺序查找要高，但折半查找只能适用于顺序存储有序表（如对线性链表就无法有效地进行折半查找）。
折半查找的C/C++代码实现：
- int binary_search(int search_table[], int length, int key)
- {
- int low = 0;
- int high = length - 1;
- while (low <= high) {
- int mid = (low + high) / 2;
- if (key == search_table[mid])
- return mid;
- else if (key < search_table[mid])
- high = mid - 1;
- else
- low = mid + 1;
- }
- return -1;
- }
这是折半查找的经典实现。不过它还有bug；效率上也还可以再改进。关于bug部分在这里做一部分摘录（如欲详细了解请见《代码之美》，效率改进详见《编程珠玑》）：
每当讨论漂亮的代码，就很容易让人联想起Jon Bentley那本经典的由Addison-Wesley出版的《Programming Pearls》 （中文名《编程珠玑》）。我就是在读那本书的时候，发现了我要找的代码例子：二分查找。
让我们快速复习一下，二分查找是一个简单而又高效的算法（但我们即将看到，要正确实现它也是有点难度的），这个算法用来确定一个预先排好顺序的数组x[0..n-1]中是否含有某个目标元素t。如果数组包含t，程序返回它在数组中的位置，否则返回-1。
Jon Bentley是这样向学生们描述该算法的：
在一个包含t的数组内，二分查找通过对范围的跟综来解决问题。开始时，范围就是整个数组。通过将范围中间的元素与t比较并丢弃一半范围，范围就被缩小。这个过程一直持续，直到在t被发现，或者那个能够包含t的范围已成为空。
他又说到：
大多数程序员认为，有了上面的描述，写出代码是很简单的事情。他们错了。能使你相信这一点的惟一方法是现在就合上书，去亲手写写代码试试看。
我的建议。如果你从来没有写过二分查找，或者有好几年没写过了，我建议你在继续读下去之前亲手写一下；它会使你对后面的内容有更深的体会。
二分查找是一个非常好的例子，因为它是如此简单，却又如此容易被写错。在《Programming Pearls》一书中，Jon Bentley记述了他是怎样在多年的时间里先后让上百个专业程序员实现二分查找的，而且每次都是在他给出一个算法的基本描述之后。他很慷慨，每次给他们两个小时的时间来实现它，而且允许他们使用他们自己选择的高级语言（包括伪代码）。令人惊讶的是，大约只有10%的专业程序员正确地实现了二分查找。
更让人惊讶的是，Donald Knuth在他的《Sorting and Searching》一书中指出，尽管第一个二分查找算法早在1946年就被发表，但第一个没有bug的二分查找算法却是在12年后才被发表出来。
然而，最让人惊讶的是，Jon Bentley正式发表的并被证明过的算法，也就是被实现或改编过成千上万次的那个，最终还是有问题的，问题发生在数组足够大，而且实现算法的语言采用固定精度算术运算的时候。
在Java语言中，这个bug导致一个ArrayIndexOutOfBoundsException异常被抛出，而在C语言中，你会得到一个无法预测的越界的数组下标。你可以在Joshua Bloch的blog上找到更多关于这个bug的信息。
bug位于这一行：
int mid = (low + high) / 2;
如果 low 和 high 的和大于Integer.MAX_VALUE（在Java中是231 -1），计算就会发生溢出，使它成为一个负数，然后被2除时结果当然仍是负数。
推荐的解决方案是修改计算中间值的方法来防止整数溢出。方法之一是用减法—而不是加法—来实现：
int mid = low + (high – low) / 2;
或者，在Java里可以使用无符号位移运算，具体参看sun微系统公司的官方bug report：
int mid = (low + high) >>> 1;
文章若无注明则属原创，转载请以链接形式注明出处。
本文地址：http://www.juliuschen.com/archives/7.html
