二分查找

	/**
	 * 有序数组递归二分查找，定位值的下标
	 * 
	 * @param arr   目标数组
	 * @param start 起始下标
	 * @param end   末尾下标
	 * @param key   查找的值
	 * @return 值的下标
	 */
	static int binarySearch(final int[] arr, int start, int end, int key) {		
		if (start > end || end >= arr.length) {
			return -1;
		}
		/* 中间位置：(end + start) / 2 等于 (end + start) >> 1 */
		int mid = (end + start) >> 1;
		if (key == arr[mid]) {
			return mid;
		}
		if (key > arr[mid]) {
			start = mid + 1;
		}else{
			end = mid - 1;
		}
		return binarySearch(arr, start, end, key);
	}

	/**
	 * 有序数组循环二分查找，定位值的下标
	 * 
	 * @param arr   目标数组
	 * @param start 起始下标
	 * @param end   末尾下标
	 * @param key   查找的值
	 * @return 值的下标
	 */
	static int binaryWhileSearch(final int[] arr, int start, int end, int key) {
		
		int mid=-1;
		do {
			if (start > end || end >= arr.length) {
				return -1;
			}
			/* 中间位置：(end + start) / 2 等于 (end + start) >> 1 */
			mid = (end + start) >> 1;
			if (key > arr[mid]) {
				start = mid + 1;
			}else if (key < arr[mid]) {
				end = mid - 1;
			}
		} while (key != arr[mid]);
		return mid;
	}