二分查找

接上回“分治法”

二分查找从实现上可以分为递归和非递归两种形式， 其算法的复杂度为 |_log n_| + 1

代码简单易懂：

public class BSearch {

	private static int[] s = { 1, 2, 3, 5, 8, 11, 21, 188, 211 };

	public static void main(String[] args) {
		System.out.println(bSearchRecursion(s, 0, s.length - 1, 11));
		System.out.println(bSearchNonRecursion(s, 0, s.length - 1, 11));
	}
	
	/**
	 * 递归
	 */
	private static int bSearchRecursion(int[] s, int low, int high, int key) {
		int mid = (low + high) / 2;
		if(s[mid] == key) return mid;
		else if(s[mid] > key) return bSearchRecursion(s, low, mid - 1, key);
		else return bSearchRecursion(s, mid -1, high, key);
	} 

	/**
	 * 非递归
	 */
	private static int bSearchNonRecursion(int[] s, int low, int high, int key) {
		while(low <= high) {
			int mid = (low + high) / 2;
			if(s[mid] == key) return mid;
			else if(s[mid] > key) high = mid - 1;
			else low = mid + 1;
		}
		
		return -1;
	}
}

由于二分查找只限于顺序存储的有序表， 对于插入、删除操作苦难。 所以其使用于不经常变动且查找频繁的有序表。