HOT100-31-在排序数组中查找元素的第一个和最后一个位置

题目描述

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

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

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

示例 1：

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

算法思路

同样，题目的难点主要是在于他的时间复杂度要求，只能是$O(logn)$，这意味着你不能去遍历这个数组，不然时间复杂度最低也是$O(n)$，但是都提示到这里了，也很难不想到二分查找，毕竟你必须得对$log$这个符号敏感！

这里我的方法比较蠢，我主要的思路是这样的：

记答案为1, 2
假如nums[mid] > target，那么1，2出现在[left, mid]
假如nums[mid] < target，那么1，2出现在[mid, right]
假如nums[mid] == target，那么左右都有可能，取左侧的第一个和右侧的最后一个即可

主要在于第三点很模糊，什么叫做“那么左右都有可能，取左侧的第一个和右侧的最后一个即可”？可以看一下这个例子：

nums = [1, 2, 3, 3, 8], nums = [1, 3, 3, 5, 8]，假设target=3。很显然二分第一轮的结果nums[mid]==3，就是中点位置，但是该向左还是右呢？这一点需要进一步判断，如果nums[mid-1]=3，那么很显然需要继续向左遍历找左端点，同理，如果nums[mid+1]=3，那么需要向右找端点，否则当前的mid就必然是左右端点。代码如下：

class Solution {
public:
    vector<int> res;
    void binaryFind(vector<int>& nums, int target, int left, int right) {
        if (left > right) {
            return;
        }
        int mid = (left + right) / 2;
        if (nums[mid] > target) {
            right = mid - 1;
            binaryFind(nums, target, left, right);
            return;
        }
        if (nums[mid] < target) {
            left = mid + 1;
            binaryFind(nums, target, left, right);
            return;
        }
        if (mid >= 1 && nums[mid-1] == target) {
            // 左侧还有，继续搜左侧
            binaryFind(nums, target, left, mid - 1);
        }
        else {
            // 左侧没有了，这是第一个
            res.push_back(mid);
        }
        if (mid + 1 < nums.size() && nums[mid+1] == target) {
            left = left + 1;
            binaryFind(nums, target, mid + 1, right);
        }
        else {
            // 右侧没有了，这是第二个
            res.push_back(mid);
        }
    }
    vector<int> searchRange(vector<int>& nums, int target) {
        // 记答案为1, 2
        // 假如nums[mid] > target，那么1，2出现在[left, mid]
        // 假如nums[mid] < target，那么1，2出现在[mid, right]
        // 假如nums[mid] == target，那么左右都有可能，取左侧的第一个和右侧的最后一个
        binaryFind(nums, target, 0, nums.size() - 1);
        return res.empty() ? vector<int>{-1, -1} : res;
    }
};

又臭又长啊！看看大神们的题解，人家直接是找第一个target和第一个大于target的数……，比我的简单多了：

class Solution {
public:
    // lower_bound 返回最小的满足 nums[i] >= target 的下标 i
    // 如果数组为空，或者所有数都 < target，则返回 nums.size()
    // 要求 nums 是非递减的，即 nums[i] <= nums[i + 1]

    int lower_bound(vector<int>& nums, int target) {
        int left = 0, right = nums.size();
        while (left < right) {
             // 循环不变量：
            // nums[left-1] < target
            // nums[right] >= target
            //最终left指向第一个大于等于的数 right也指向left
            int mid = left + ((right - left) >> 1) ;
            if ( nums[mid] < target) {
                left = mid + 1;
            }else {
                right = mid; 
            }
        }
        return left;
    }

    vector<int> searchRange(vector<int>& nums, int target) {
        int start = lower_bound(nums, target);
        if (start == nums.size() || nums[start] != target) {
            return {-1, -1};
        }
        int end = lower_bound(nums, target + 1) - 1;
        return {start, end};
    }
};