二分查找(BinarySearch)

• 每次都要缩减搜索区域
• 每次缩减不能排除潜在答案

循环条件：left<=right;

缩减搜索空间：left=mid+1,r=mid-1;

public int search(int target,int[] arr){
	int left=0,right=arr.length-1;
    while(left<=right){
        int mid=left+(right-left)/2;
        if(arr[mid]==target){
            return mid;
		}else if(arr[mid]>target){
            return right=mid-1;
        }else{
            return left=mid+1;
        	}
        }
	}
	return -1;
}

递归的写法：

public static int search(int target,int start,int end,int[] arr) {
		if(start>end) return -1;
		int mid=start+(end-start)/2;
		if(arr[mid]==target) return mid;
		if(arr[mid]>target) {
			return search(target, start, mid-1, arr);
		}else {
			return search(target, mid+1, end, arr);
		}
	}

循环条件：left

缩减搜索空间：left=mid+1,r=mid-1;

public int search(int target,int[] arr){
	int left=0,right=arr.length-1;
    while(left 
2最后出现的一个位置： 
public int search(int target,int[] arr){
	int left=0,right=arr.length-1;
    while(lefttarget){
            right=mid-1;
		}else{
           left=mid;
        }
	}
	return 1;
}
 
万用型： 
循环条件：left 
缩减搜索空间：left=mid,r=mid；
 
最接近2的数： 
public int search(int target,int[] arr){
	int left=0,right=arr.length-1;
    while(leftk){
        return l;
    }else{
        return k-arr[l]