二分查找算法

摘自java.util.Arrays的代码：

    public static int binarySearch(int[] a, int key) {
	int low = 0;
	int high = a.length-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.
    }

注意：第6行，用的是位移的操作，当然，我们明白二进制数右移1位相当于除2，用位移就是怕“精度”出问题导致意外的BUG。

 

http://hi.baidu.com/xuwu125/blog/item/4db3b8af78ceb2cf7cd92aff.html/cmtid/27baac0e8b9f2bed37d12267

这个帖子曾经提到的BUG已经解决了，就是用位移代替除的操作。