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

题目

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

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

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

示例

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

输入：nums = [], target = 0
输出：[-1,-1]
1
2
3
4
5

思路

二分查找思路解释：

1. 首先判断数组是否为空，如果为空，则直接返回 {-1, -1}，表示找不到目标值在数组中的范围。
2. 初始化一个长度为 2 的结果数组 result，初始值为 {-1, -1}，用于存储最终的结果。
3. 使用二分查找的思想，在数组 nums 中寻找目标值的起始位置：
   • 初始化搜索范围为 [0, n-1]，其中 n 为数组长度。
   • 不断缩小搜索范围，直到左指针 l 和右指针 r 相遇。
   • 在每一步中，计算中间位置 mid，并根据 nums[mid] 与目标值 target 的关系调整左右指针的位置。
   • 最终得到的 l 即为目标值的起始位置，如果 nums[l] 不等于目标值，则说明数组中不存在目标值，直接返回 {-1, -1}。
4. 如果找到了目标值的起始位置，将其存储在 result[0] 中。
5. 然后重新初始化左右指针，进行二分查找目标值的结束位置：
   • 同样采用二分查找的思想，在数组中寻找目标值的结束位置。
   • 不断缩小搜索范围，直到左指针 l 和右指针 r 相遇。
   • 在每一步中，计算中间位置 mid，并根据 nums[mid] 与目标值 target 的关系调整左右指针的位置。
   • 最终得到的 l 即为目标值的结束位置。
6. 将结束位置存储在 result[1] 中，最终返回 result。

这样，代码通过两次二分查找，可以找到目标值在数组中的起始位置和结束位置，并且满足了 O(log n) 的时间复杂度要求。

Code

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

下面是代码的执行效率

当然我们也可以用更简便的二分查找lower_bound() 和 upper_bound()函数求解：

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        auto first = lower_bound(nums.begin(), nums.end(), target);
        auto last = upper_bound(nums.begin(), nums.end(), target);
        
        if (first == nums.end() || *first != target) {
            return {-1, -1};
        } else {
            return {static_cast<int>(first - nums.begin()), static_cast<int>(last - nums.begin() - 1)};
        }
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13

这段代码实现了在一个按非递减顺序排列的整数数组中查找目标值的起始位置和结束位置，使用了 C++ 标准库中的 lower_bound() 和 upper_bound() 函数。下面是代码的解释：

1. 首先，使用 lower_bound(nums.begin(), nums.end(), target) 函数在排序后的数组 nums 中找到第一个不小于目标值 target 的元素的迭代器，赋值给变量 first。

2. 然后，使用 upper_bound(nums.begin(), nums.end(), target) 函数在排序后的数组 nums 中找到第一个大于目标值 target 的元素的迭代器，赋值给变量 last。

3. 接着，通过比较 first 是否等于 nums.end() 或 *first 是否等于 target，来判断是否找到了目标值：

   • 如果 first == nums.end()，表示没有找到目标值，直接返回 {-1, -1}。
   • 如果 *first != target，表示没有找到目标值，直接返回 {-1, -1}。
   • 否则，继续执行下面的逻辑。

4. 最后，根据找到的位置返回结果：

   • 返回 {static_cast(first - nums.begin()), static_cast(last - nums.begin() - 1)}，即将第一个出现位置和最后一个出现位置的下一个位置转换为整数，并放入结果数组中返回。

通过使用 lower_bound() 和 upper_bound() 函数，可以非常简洁地实现在排序数组中查找目标值的起始位置和结束位置，避免了手动编写二分查找的复杂逻辑。

但是执行效率不如手写二分查找高