二分搜索算法

	public int binarySearch(int[] a, int searchKey) {
		int lowerBound = 0;
		int upperBound = a.length - 1;
		int curIn;

		while (true) {
			curIn = (lowerBound + upperBound) / 2;
			if (a[curIn] == searchKey)
				return curIn;
			else if (lowerBound > upperBound)
				return -1;
			else {
				if (a[curIn] < searchKey)
					lowerBound = curIn + 1;
				else
					upperBound = curIn - 1;
			}
		}
	}

二分搜索的算法是，将n个元素分成个数大致相同的两半，取a[n/2]与欲查找的key作比较，如果key=a[n/2]则找到x，算法终止。如果key<a [n/2]，则我们只要在数组a的左半部继续搜索key（这里假设数组元素呈升序排列）。如果key>a[n/2]，则我们只要在数组a的右半部继续搜索 key。
对于算法复杂度的比较：O(1) < O(logN) < O(N) < O(N^2)。
二分查找算法具有很高的效率，它的算法复杂度为O(lngN)。

评论

1 楼 marlgl 2008-10-16  

7        curIn = (lowerBound + upperBound) / 2;  

 int mid = (low + high) / 2;

当low+high的值超过了最大的正int值 (Math.pow(2, 31)- 1) 的时候, mid会变成负值

很简单, 修改这行语句为:

            int mid = low + ((high - low) / 2);
或者
             int mid = (low + high) >>> 1;

参看：http://blog.csdn.net/longing_chen/archive/2006/06/10/785570.aspx