[数据结构与算法]数据结构---二分查找

方式一：递归实现二分查找

解释：

• arr int型数组
• elemen 需要查找的元素
• left 数组的左下标（初始值为0）
• right是数组的右下标（初始值为数组长度减一(arr.length-1)）

	public static int binarySearch(int[] arr, int element, int left, int right) {
//		异常数据处理
		if (element < arr[left] || element > arr[right] || left > right) {
			return -1;
		}
		int middle = left + ((right - left) / 2);// 等同于 (left + right) / 2，防止溢出
//		大了右减1，小了左加1
		if(arr[middle] == element) return middle;
		if (arr[middle] > element) {
			return binarySearch(arr, element, left, middle - 1);
		} else if (arr[middle] < element) {
			return binarySearch(arr, element, middle + 1, right);
		} else {
			return middle;
		}
	}

方式二：简单判断(if…else)实现二分查找

解释：

• array int型数组
• element 所要查找的元素

	public static int search(int[] array,int element) {
		int left = 0;
		int right = array.length - 1; // 定义了target在左闭右闭的区间内，[left, right]
		while (left <= right) { // 当left == right时，区间[left, right]仍然有效
			int middle = left + ((right - left) / 2);// 等同于 (left + right) / 2，防止溢出
			if (array[middle] == element)
				return middle;
			if (array[middle] > element) {
				right = middle - 1; // target在左区间，所以[left, middle - 1]
			} else if (array[middle] < element) {
				left = middle + 1; // target在右区间，所以[middle + 1, right]
			} else { // 既不在左边，也不在右边，那就是找到答案了
				return middle;
			}
		}
		return -1;// 没有找到目标值
	}