二分查找

1. 二分查找

非递归

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

递归

public int search(int[] nums, int target) {
        if(null==nums||0==nums.length){
            return -1;
        }
        
        return binaryS(nums,0,nums.length-1,target);
    }
    private int binaryS(int[] nums,int left,int right,int target){
        if(left>right){
            return -1;
        }
        int mid = (left+right)/2;
        if(nums[mid]==target){
            return mid;
        }
        if(nums[mid]<target){
            return binaryS(nums,mid+1,right,target);
        }
        return binaryS(nums,left,mid-1,target);
    }

2. 变形查找第一个值等于给定值的元素

    private int bSearchFirst(int[] nums,int target){
        if(null==nums||0==nums.length){
            return -1;
        }
        int left = 0;
        int right = nums.length-1;
        while(left<= right){
            int mid = (left+right)/2;
            if(nums[mid] >target){
                right = mid-1;
            }
            else if(nums[mid]<target) {
                left = mid+1;
            }
            else if((mid==0)||(nums[mid-1]!=target)){//如果nums[mid]=target,而且是第一个
                    return mid;
            }
            else{//如果nums[mid]=target,而且不是第一个
                right = mid-1;
            } 
        }
        return -1;
    }

3. 变形查找最后一个值等于给定值的元素

    private int bSearchLast(int[] nums,int target){
        if(null==nums||0==nums.length){
            return -1;
        }
        int left = 0;
        int right = nums.length-1;
        while(left<= right){
            int mid = (left+right)/2;
            if(nums[mid] >target){
                right = mid-1;
            }
            else if(nums[mid]<target){
                left = mid+1;
            }
            else if((mid==nums.length-1)||(nums[mid+1]!=target)){//如果nums[mid]=target,而且是最后一个
                    return mid;
            }
            else {//如果nums[mid]=target,而且是最后一个
                left = mid+1;
            }
        }
        return -1;
    }

4.变形查找第一个大于等于给定值的元素

public int searchInsert(int[] nums, int target) {
        if(null == nums || 0== nums.length){
            return -1;
        }
        int left =0;
        int right =nums.length-1;
        while(left<=right){
            int mid = left+((right-left)>>1);
            if(nums[mid]<target){
                left = mid+1;
            }
            else if(mid ==0|| nums[mid-1]<target){//若干是第一个大于等于target的值
                return mid;
            }
            else{
                right = mid-1;
            }
        }
        return nums.length;
    }

5. 变形查找最后一个小于等于给定值的元素

上一个变形的结果-1，或使用

public int search(int[] nums, int target) {
        if(null == nums || 0== nums.length){
            return -1;
        }
        int left =0;
        int right =nums.length-1;
        while(left<=right){
            int mid = left+((right-left)>>1);
            if(nums[mid]>target){
                right = mid-1;
            }
            else if(mid ==nums.length-1|| nums[mid+1]>target){//若干是第一个大于等于target的值
                return mid;
            }
            else{
                left = mid+1;
            }
        }
        return -1;
    }