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

深藏阁楼爱情的钟 2022-11-16 15:21 144阅读 0赞

### 题目描述 ###

给定一个按照升序排列的整数数组 `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`

### 解题思路 ###

【有序数组】【log n时间复杂度】自然而然的会去向二分法靠拢。

### 二分模板 ###

二分的代码精简漂亮，是很多互联网公司面试喜欢考察的题目类型之一，但是很多人写二分多多少少会出bug，下面总结了两种情况下的二分模板。

二分模板一共有两个，分别适用于不同情况。  
算法思路：假设目标值在闭区间`[l, r]`中， 每次将区间长度缩小一半，当`l = r`时，我们就找到了目标值。

### 版本1 ###

当我们将区间`[l, r]`划分成`[l, mid]`和`[mid + 1, r]`时，其更新操作是`r = mid`或者`l = mid + 1;`，计算`mid`时不需要加1。

##### C++ 代码模板： #####

int bsearch_1(int l, int r)
    {
        while (l < r)
        {
            int mid = l + r >> 1;
            if (check(mid)) r = mid;
            else l = mid + 1;
        }
        return l;
    }

### 版本2 ###

当我们将区间`[l, r]`划分成`[l, mid - 1]`和`[mid, r]`时，其更新操作是`r = mid - 1`或者`l = mid;`，此时为了防止死循环，计算`mid`时需要加1。

##### C++ 代码模板： #####

int bsearch_2(int l, int r)
    {
        while (l < r)
        {
            int mid = l + r + 1 >> 1;
            if (check(mid)) l = mid;
            else r = mid - 1;
        }
        return l;
    }

\*\*版本一、版本二还有一个区别：答案所在区间端点不同。 \*\*

### AC代码 ###

class Solution {
        
    public:
        vector<int> searchRange(vector<int>& nums, int target) {
        
            if(!nums.size()) return {
        -1, -1};
            int l = 0, r = nums.size() - 1;
            while(l < r){
        
                int mid = (l + r) >> 1;
                if(nums[mid] < target) l = mid + 1;
                else r = mid;
            }
            if(nums[r] != target) return {
        -1, -1};
            vector<int> res;
            res.push_back(r);
    
            l = 0;
            r = nums.size() - 1;
            while(l < r){
        
                int mid = (l + r + 1) >> 1;
                if(nums[mid] <= target) l = mid;
                else r = mid - 1;
            }
            res.push_back(l);
    
            return res;
        }
    };