Java算法--第二章--查找与排序（3）二分法查找递归方法

Java算法–第二章–查找与排序（3）二分法查找递归方法

全范围的二分查找
等价于三个子问题：
1.左边找（递归）
2.中间比
3.右边找（递归）
注意：前提是所查找的内容必须是有序的，且左边和右边查找只取其中的一个分支

代码：

package section02;

public class 二分法查找 {
	public static void main(String[] args) {
		int[] arr = new int[] { -98, -34, 2, 34, 54, 66, 79, 105, 210, 333 };
		int i = binarySearch1(arr, 0, arr.length, 54);
		System.out.println("要查找的数位置为：" + i);
	}

	/*
	 * 二分法查找递归解法
	 */
	private static int binarySearch1(int[] arr, int low, int high, int key) {
		if (low > high)
			return -1;
		int mid = low + ((high - low) >> 1);// (high - low) >> 1为防止溢出，以为也更加高效
		int midVal = arr[mid];
		if (midVal < key)
			return binarySearch1(arr, mid + 1, high, key);
		else if (midVal > key)
			return binarySearch1(arr, low, mid - 1, key);
		else
			return mid;
	}
}

输出：

要查找的数位置为：4