二分查找

BinarySearch.java

class BinarySearch {
	/*
   * 在已排序数组中找到 key 的 index,如果找不到则返回小于 key 的个数
   * @param a 已排序数组
   * @param key 目标值
   */

	public static int binarySearchRecursion(int[] a,int key) {
		return binarySearchRecursionHelper(a,key,0,a.length-1);
	}

	private static int binarySearchRecursionHelper(int[] a,int key,int lo,int hi) {
		if (lo > hi) return lo;  // 没找到就返回小于 key 的数量
		int mid = lo + (hi - lo) /2;
		if (key > a[mid]) return binarySearchRecursionHelper(a,key,mid + 1,hi);
		else if (key < a[mid]) return binarySearchRecursionHelper(a,key,lo,mid - 1);
		else return mid;
	}

	public static int binarySearchIteration(int[] a,int key) {
		int lo = 0;
		int hi = a.length - 1;
		while (lo <= hi) {
			int mid = lo + (hi - lo) /2;
			if (key > a[mid]) lo = mid + 1;
			else if (key < a[mid]) hi = mid - 1;
			else return mid;
		}
		return lo;  // 没找到就返回小于 key 的数量
	}
	public static void main(String[] args) {
		int[] a = new int[]{1,5,7,9,14,16,58,333,6666,13312};
		System.out.println(binarySearchRecursion(a,14));
	}
}