【来不及刷题之】32、二分搜索（寻找数，寻找左右边界）

1. 基础二分搜索：寻找一个数

一道很基础的题目，主要注意一下循环条件是 left<=right 即可

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

2. 寻找左边界 或 右边界

下面用这个题目将寻找左右边界的算法进行整理

🍓注意事项：

• 循环条件全部都是left<=right
• 寻找左边界：收缩有边界
• 寻找右边界：收缩左边界
• 寻找左右边界不再是返回-1，左边界返回left，右边界返回right
• 但是在返回之前，都需要先进行一次越界判断

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int left_bound=findLeftBound(nums,target);
        int right_bound=findRightBound(nums,target);
        return new int[]{left_bound,right_bound};
    }

    int findLeftBound(int[] nums, int target){
        int left=0;
        int right=nums.length-1;
        while(left<=right){
            int mid=left+(right-left)/2;
            if(nums[mid]==target){
                right=mid-1; // 寻找左边界：不断收缩右边界
            }else if(nums[mid]<target){
                left=mid+1;
            }else{
                right=mid-1;
            }
        }
        //因为寻找的是左边界，所以返回左边界的值
        //为了防止nums[left]越界，需要在返回前进行一次边界判断
        if(left==nums.length)
            return -1;
        return nums[left]==target?left:-1;
    }

       int findRightBound(int[] nums, int target){
        int left=0;
        int right=nums.length-1;
        while(left<=right){
            int mid=left+(right-left)/2;
            if(nums[mid]==target){
                left=mid+1; // 寻找右边界：不断收缩左边界
            }else if(nums[mid]<target){
                left=mid+1;
            }else{
                right=mid-1;
            }
        }
        //因为寻找的是右边界，所以返回右边界的值
        //为了防止nums[right]越界，需要在返回前进行一次边界判断
        if(right==-1)
            return -1;
        return nums[right]==target?right:-1;
    }
}