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

难度：中等

给你一个按照 非递减顺序 排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target，返回 [-1, -1]。

你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。

示例 1：

输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]

示例 2：

输入：nums = [5,7,7,8,8,10], target = 6
输出：[-1,-1]

示例 3：

输入：nums = [], target = 0
输出：[-1,-1]

提示：

• 0 <= nums.length <= 105
• -109 <= nums[i] <= 109
• nums 是一个非递减数组
• -109 <= target <= 109

解题思路

一开始想到了快慢指针法，一个保留给定目标值的开始位置，一个寻找给定目标值的结束位置，但这样的时间复杂度显然是 O(n)，不满足题目需求。

因为数组有序且要求时间复杂度为 O(log n)，考虑一下二分法。

我的思路：

1. 基础的二分查找中，我们找到 target 时算法就结束了，但这题我们需要做些处理
2. 如果我们想找最左边等于 target 的值，那么一开始在数组中找到 target 的时候，并不代表我们已经找到了左边界
3. 虽然此时 middle 指向的值等于 target 了，但是我们要找的值可能还在 middle 左边
4. 为了总体上达到 O(log n) 的时间复杂度，我们选择继续使用二分法，做法是更新 right = middle - 1 后继续查找
5. 循环退出的条件是 left > right，此时 left 所指向的，就是左边界
6. 右边界的查找同理，只是第 4 步的更新操作改为 left = middle + 1，第 5 步中 right 所指向的，就是右边界

你也许会说，找到第一个 target 的时候，然后向左或向右线性搜索不行吗？代码可行，但是这样时间复杂度就成了 O(n + log n)，而不是 O(log n)。

我的代码

public int[] searchRange(int[] nums, int target) {
    int left = 0;
    int right = nums.length - 1;
    return new int[]{getLeftBorder(nums, left, right, target), getRightBorder(nums, left, right, target)};
}

public int getLeftBorder(int[] nums, int left, int right, int target) {
    int leftBound = -1; // 记录一下没有找到左边界的时候的情况
    while (left <= right) {//退出循环的时候，是right跑到了left左边的时候
        int middle = left + (right - left) / 2;
        if (nums[middle] == target) {
            leftBound = middle; //此时更新leftBound，可以保证最后一次更新的时候，leftBound是我们需要的左边界
            right = middle - 1;
        } else if (nums[middle] < target) {
            left = middle + 1;
        } else if (nums[middle] > target) {
            right = middle - 1;
        }
    }
    return leftBound;
}

public int getRightBorder(int[] nums, int left, int right, int target) {
    int rightBound = -1;
    while (left <= right) {
        int middle = left + (right - left) / 2;
        if (nums[middle] == target) {
            rightBound = middle;
            left = middle + 1;
        } else if (nums[middle] < target) {
            left = middle + 1;
        } else if (nums[middle] > target) {
            right = middle - 1;
        }
    }
    return rightBound;
}

时间复杂度：O(log n)

空间复杂度：O(1)

这份代码在简洁性上很有大的优化空间，例如可以把寻找左右边界的方法合并，写成一个通用的方法，但拆开写，逻辑其实会更清晰一些。

总结

刚接触二分搜索的时候，不应该上来就想用一个二分法来查找左右边界，很容易把自己绕进去。扎扎实实写两个二分法来分别找左、右边界，逻辑会更加清晰。