1、前言

2、思路

思路就是对左右两边都进行二分查找，确定左右边界。即对数组进行两次二分查找，首先对数组进行二分查找，确定左边界。确定左边界的方法是，如果遇到 nums[mid] == target，此时不需要返回，而是把右边界往左缩，即 right = mid - 1。while 循环条件是 left <= right，即 right 会减到 left > right，跳出循环。有人会怀疑将边界往左锁 right = mid - 1 会使得 left 不能到 target 的左边界去。不会出现这种情况，right 最终会到左边界的上一位，然后 left 最终会与 right 相等。当 left 到达左边界时，left > right 会跳出循环，所以 left 会是左边界。

还有一种简单的方法是，找到 target 后，定义两个指针不断向两边扩展，但是这种扩展的方法确实没有二分快。但是如果想不出来，而是用扩展的方法吧，解出题还是好的。

3、代码

class Solution {
    public int[] searchRange(int[] nums, int target) {
        if(nums == null || nums.length == 0){
            return new int[]{-1,-1};
        }
        int start = leftSearch(nums,target);
        if(start == -1){
            return new int[]{-1,-1};
        }
        int end = rightSearch(nums,target);
        return new int[]{start,end};
    }

    int leftSearch(int[] nums, int target) {
        int left = 0, 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) {
                right = mid - 1;
            } else if (nums[mid] == target) {
                // 别返回，收缩左侧边界
                right = mid - 1;
            }
        }
        // 最后要检查 left 越界的情况
        if (left >= nums.length || nums[left] != target)
            return -1;
        return left;
    }


    int rightSearch(int[] nums, int target) {
        int left = 0, 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) {
                right = mid - 1;
            } else if (nums[mid] == target) {
                // 别返回，收缩右侧边界
                left = mid + 1;
            }
        }
        // 最后要检查 right 越界的情况
        if (right < 0 || nums[right] != target)
            return -1;
        return right;
    }
}

public class Q34_SearchRange {

    public int[] searchRange(int[] nums, int target) {
        if(nums == null || nums.length == 0){
            return new int[]{-1, -1};
        }

        int mid = binarySearch(nums, target);
        if(mid == -1){
            return new int[]{-1, -1};
        }

        int left = mid, right = mid;
        while((left - 1 >= 0 && nums[left - 1] == nums[left]) || (right + 1 <= nums.length - 1 && nums[right] == nums[right + 1])){
            if(left - 1 >= 0 && nums[left - 1] == nums[left]){
                left--;
            }
            if(right + 1 <= nums.length && nums[right] == nums[right + 1]){
                right++;
            }
        }

        return new int[]{left, right};
    }

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

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

            if(nums[mid] == target){
                return mid;
            }else if(nums[mid] > target){
                right = mid - 1;
            }else if(nums[mid] < target){
                left = mid + 1;
            }
        }

        return -1;
    }
    

    public static void main(String[] args) {
        int[] nums = {1};
        int target = 1;
        int[] res = new Q34_SearchRange().searchRange(nums, target);
        System.out.println(res[0] + ":" + res[1]);
    }
}