常用二分查找模板

//二分查找各种情况编写练习

public class BinarySearch {

//精确查找---用递归实现二分查找，精确查找目标元素的位置,假定数组递增排列，且不存在重复元素
	public int bsearch1(int array[],int low,int high,int target){
		if(low > high) return -1;

		int mid = low + (high - low)/2;
		if(array[mid] > target){
			return bsearch1(array,low,mid-1,target);
		}
		if(array[mid] < target){
			return bsearch1(array,mid+1,high,target);
		}
		return mid;
	}

//精确查找---用迭代的方式实现二分查找，精确查找目标元素的位置,假定数组递增排列，且不存在重复元素
	public int bsearch2(int array[],int low,int high,int target){
		while(low <= high){
			int mid = low + (high - low)/2;
			if(array[mid] > target){
				high = mid -1;
			}
			else if(array[mid] < target){
				low = mid + 1;
			}
			else{
				return mid;
			}
		}
		return -1;
	}

//界限查找----用二分查找寻找上届，正好大于目标数的那个数(严格界限，不包含自身)
	public int bsearchupperbound(int array[],int low,int high,int target){
		if(low > high || target >= array[high]){
			return -1;
		}


		while(low < high){
			int mid = low + (high - low)/2;
			if(array[mid] > target){
				high = mid;
			}
			else{
				low = mid + 1;
			}
		}
		return high;
	}

//界限查找---用二分查找寻找下届，正好小于目标数的那个数(严格界限，不包含自身)
	public int bsearchlowerbound(int array[],int low,int high,int target){
		if(low > high || target <= array[low]){
			return -1;
		}

		while(low < high){
			int mid = (low + high + 1) / 2;		//这里用向上取整，否则陷入死循环 因为low无法往上爬超过high

			if(array[mid] < target){
				low = mid;
			}
			else{
				high = mid -1;
			}
		}
		return low;
	}

//界限查找---用二分查找寻找上届，正好大于等于目标数的那个数(松散界限，可以包含自身)
	public int bsearch5(int array[], int low,int high,int target){
		if(low > high || target > array[high]){
			return -1;
		}
		while(low < high){
			int mid = low + (high -low)/2;
			if(array[mid] >= target){
				high = mid;
			}
			else{
				low = mid + 1;
			}
		}
		return high;
	}

//界限查找---用二分法寻找下届，正好小于等于目标的那个数	(松散界限，可以包含自身)
	public int bsearch6(int array[],int low,int high,int target){
		if(low > high || target < array[low]){
			return -1;
		}
		while(low < high){
			int mid = (low + high + 1)/2;
			if(array[mid] <= target){
				low = mid;
			}
			else{
				high = mid - 1;
			}
		}
		return low;
	}
//用二分查找找寻区域，找到目标元素出现的下标范围，允许重复元素(先找到严格上届和严格下届)
	public int[] searchRange(int[] array, int low, int high,int target){
		int[] results = {-1,-1};
		if(low > high){
			return results;
		}
		int lower = bsearchlowerbound(array, 0, array.length -1, target);
		lower = lower + 1;
		if(array[lower] == target){
			results[0] = lower;
		}
		else{
			return results;
		}

		int upper = bsearchupperbound(array, 0, array.length - 1, target);
		upper = upper < 0 ? (array.length - 1) : (upper -1);

		results[1] = upper;

		return results;

	}

例题