java二分查找法

【二分查找要求】：

1.必须采用顺序存储结构

 2.必须是有序的数组

首先先看看普通的搜索方法

/**
	 * 普通方法的查找
	 * 
	 * @param arr
	 * @param value
	 * @return
	 */
	public static int search(int[] arr, int value) {
		for (int i = 0; i < arr.length; i++) {
			if (arr[i] == value) {
				return i;
			}
		}
		return -1;
	}

看看二分查找

/**
	 * 二分查找方法
	 * 
	 * @param arr
	 *            目标数组
	 * @param value目标要查找的值
	 * @return
	 */
	public static int binarySearch(int[] arr, int value) {
		int low = 0;

		int high = arr.length - 1;

		int middle;

		while (low <= high) {
			middle = (low + high) / 2;

			if (arr[middle] == value) {
				return middle;
			} else if (arr[middle] > value) {
				// 说明要查找的值在中间的左边
				high = middle - 1;
			} else {
				// 说明要查找的值在中间的右边
				low = middle + 1;
			}
		}

		return -1;
	}

/**
	 * 递归算法，二分查找
	 * @param arr
	 * @param value
	 * @param low
	 * @param high
	 * @return
	 */
	public static int binarySearch(int[] arr,int value,int low,int high){
		int middleIndex = (low + high)/2;
		
		if(value < arr[low] || value > arr[high] || low > high){
			return -1;
		}
		
		if(value < arr[middleIndex]){
			//说明要查找的值在中间的左边
			return binarySearch(arr, value, low, middleIndex-1);
		}else if(value > arr[middleIndex]){
			//说明要查找的值在中间的右边
			return binarySearch(arr, value, middleIndex + 1, high);
		}else{
			//说明找到了该值,返回该值在数组中的索引
			return middleIndex;
		}
	}