二分查找
接上回“分治法”二分查找从实现上可以分为递归和非递归两种形式， 其算法的复杂度为 |_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 == key) return mid;else if(s > 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 == key) return mid;else if(s > key) high = mid - 1;else low = mid + 1;}return -1;}}
由于二分查找只限于顺序存储的有序表， 对于插入、删除操作苦难。 所以其使用于不经常变动且查找频繁的有序表。
页:
[1]