【二分查找】34. 在排序数组中查找元素的第一个和最后一个位置

34. 在排序数组中查找元素的第一个和最后一个位置

解题思路

• 改造二分查找算法
• 寻找目标的左边界
• 寻找目标的右边界

class Solution {
    public int[] searchRange(int[] nums, int target) {
        // 二分查找的搜索左边界和搜索有边界
        int left = left_bound(nums,target);
        int right = right_bound(nums,target);
        return new int[]{left,right};

    }

    int left_bound(int[] nums,int target){
        int left = 0;
        int right = nums.length - 1;

        while(left <= right){
            int mid = (right - left) / 2 + left;

            if(nums[mid] < target){
                left = mid + 1;
            }else if(nums[mid] > target){
                right = mid - 1;
            }else if(nums[mid] == target){
                // 寻找左边界 那么需要收缩右边界
                right = mid - 1;
            }
        }

        if(left >= nums.length || nums[left] != target){
            return -1;
        }

        return left;
    }

    int right_bound(int[] nums,int target){
        int left = 0;
        int right = nums.length - 1;

        while(left <= right){
            int mid = (right - left) / 2 + left;

            if(nums[mid] < target){
                left = mid + 1;
            }else if(nums[mid] > target){
                right = mid - 1;
            }else if(nums[mid] == target){
                // 寻找右边界 那么收缩左边界
                left = mid + 1;
            }
        }

        if(right < 0 || nums[right] != target){
            return -1;
        }

        return right;
    }
}