二分查找

递归方法：

public static int search(int[] array, int start, int end, int val) {
	int mid = (end + start) / 2;
	if (array[mid] == val) {
		return mid;
	}
	if (array[mid] > val) {
		end = mid - 1;
	}
	if (array[mid] < val) {
		start = mid + 1;
	}
	int r = search(array, start, end, val);
	if (r >= 0) {
		return r;
	}
	return -1;
}

非递归：

public static int search2(int[] array, int val) {
	int start = 0;
	int end = array.length - 1;
	while (end >= start) {
		int mid = (end + start) / 2;
		if (array[mid] == val) {
			return mid;
		}
		if (array[mid] > val) {
			end = mid - 1;
		}
		if (array[mid] < val) {
			start = mid + 1;
		}
	}
	return -1;
}