二分查找

    接上回“分治法”

二分查找从实现上可以分为递归和非递归两种形式， 其算法的复杂度为 |_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;	}}

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