admin管理员组

文章数量:1444900

【二分查找】模板题：在排序数组中查找元素的第一个和最后一个位置

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

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

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

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

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

示例 1：

代码语言：javascript代码运行次数：0运行复制
输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]

示例 2：

代码语言：javascript代码运行次数：0运行复制
输入：nums = [5,7,7,8,8,10], target = 6
输出：[-1,-1]

示例 3：

代码语言：javascript代码运行次数：0运行复制
输入：nums = [], target = 0
输出：[-1,-1]

提示：

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

解题思路

​ 这道题算是找区间的左右端点的模板题，但是细节非常的多，我们必须要搞清楚，而不是去背模板，虽说模板代码很少，但是一定要理解！这道题用的还是二分思想，就是根据数据的性质，在某种判断条件下将区间一分为二，然后舍去其中一个区间，然后再另一个区间内查找；

​ 如果我们想一次性找到左右边界，那么是非常难的，所以我们干脆拆开求左右区间，这样子省事多了！

​ 为了方便叙述，下面统一用 target 表示该元素， resLeft 表示左边界， resRight 表示右边界。

1、寻找左边界思路

​ 我们可以将数组划分为下面两个区间：

  • 左区间 [left, resLeft - 1] 区间都是小于 target 的
  • 右区间（包括左边界） [resLeft, right] 都是大于等于 target 的

因此对于 mid 来说，我们可以分为下面的两种情况来讨论：

  1. 当 mid 落在 [left, resLeft - 1] 区间时，说明该区间元素都是小于 target 的，此时 [left, mid] 区间是可以舍弃的，所以 left = mid + 1。
  1. 当 mid 落在 [resLeft, right] 区间时，因为有可能 nums[mid] > target，所以 不能直接返回结果。并且我们也 不能直接让 right = mid - 1，因为万一 mid 就是最左端点的话，我们让 right 跳过去，那不就是错过了吗（这和我们的条件判断有关系），对不对，所以对于该情况我们采用的方式 right = mid。

​ 接下来就是处理细节问题：

  1. 终止循环条件：必须是 left < right，而不能是 left ≤ right
    • 要处理这个问题的话，我们需要结合双指针移动情况来看看是否能成立。当 left == right 的时候，并且还一直让 nums[mid] ≥ target 成立的话，此时就会 陷入死循环，如下图所示，所以我们不能让 left 等于 right，这是根据我们双指针的移动来的，不一定每种解法都是不能等于的，所以不能背题，要理解！

  1. 求中点的操作：必须是 left + (right - left) / 2，而不能是 left + (right - left + 1) / 2
    • 我们之前在学朴素二分模板的时候介绍过这个写法，它们求出来的位置其实不太一样，如下所示：

  • 如果选择表达式 left + (right - left) / 2 的话，假设此时 left 和 right 已经走到相邻位置，用表达式求出来的 mid 是 靠左 的，也就是 left 位置处
    • 如果 nums[mid] < target 的话，那么直接 left = mid + 1 就遇到 right，直接终止了。
    • 如果 nums[mid] >= target 的话，那么 right = mid，那么 right 就会遇上 left，也直接终止了。

  • 如果选择表达式 left + (right - left + 1) / 2 的话，假设此时 left 和 right 已经走到相邻位置，用表达式求出来的 mid 是 靠右 的，也就是 right 位置处
    • 如果 nums[mid] < target 的话，那么直接 left = mid + 1 跳过 right，就终止了。
    • 如果 nums[mid] >= target 的话，那么 right = mid，此时就不行了，相当于 left 和 right 一直没动，而 mid 也就不会动，就导致了 死循环！

总结上述的细节，就是两点：

  1. 终止循环条件：left < right
  2. 求中点操作：left + (right - left) / 2

2、寻找右边界思路

​ 右边界其实就是左边界相反过来啦，懂了左边界的求法，右边界自然就懂了，只不过它们之间还是有细节之分的，主要体现在 求中点操作！

​ 我们可以将数组划分为下面两个区间：

  • 左区间（包括右边界） [left, resLeft] 区间都是小于等于 target 的
  • 右区间 [resLeft + 1, right] 都是大于 target 的

因此对于 mid 来说，我们可以分为下面的两种情况来讨论：

  1. 当 mid 落在 [resLeft + 1, right] 区间时，说明该区间元素都是大于 target 的，此时 [mid, right] 区间是可以舍弃的，所以 right = mid-1。
  2. 当 mid 落在 [left, resLeft] 区间时，因为有可能 nums[mid] < target，所以 不能直接返回结果。并且我们也 不能直接让 left= mid + 1，因为万一 mid 就是最右端点的话，我们让 left 跳过去，那就是错过了，所以对于该情况我们采用的方式 left = mid。

​ 接下来就是处理细节问题：

  1. 终止循环条件：必须是 left < right，而不能是 left ≤ right
    • 这个和处理左边界是一模一样的，具体的可以参考上面讲左边界求法中的细节处理，那里有讲为什么不能 left == right。
  2. 求中点的操作：必须是 left + (right - left + 1) / 2，而不能是 left + (right - left) / 2
    • 注意注意，这点和求左边界的时候是不同的，不要搞成同一个了！这里我们直接列举为什么不加一的表达式不行，更具体的解析可以自动动手做一下，和上面求左边界是类似的！
    • 如果选择表达式 left + (right - left) / 2 的话，假设此时 left 和 right 已经走到相邻位置，用表达式求出来的 mid 是 靠左 的，也就是 left 位置处
      • 此时如果 nums[mid] > target 的话，那么直接 right = mid - 1 就和 left 相遇了，直接终止，这没错。
      • 但如果此时 nums[mid] <= target 的话，那么走的 left = mid，此时 left 一直不动，那么 mid 就不动，就直接 死循环 了！

总结上述的细节，就是两点：

  1. 终止循环条件：left < right
  2. 求中点操作：left + (right - left + 1) / 2

​ 剩下的就是根据题目需要的返回值，然后设置返回值细节进行返回即可！

代码语言：javascript代码运行次数：0运行复制
class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) 
    {
        if(nums.size() == 0)
            return { -1, -1 };
        return { findLeft(nums, target), findRight(nums, target) };
    }
    
    // 查找区间的左端点
    int findLeft(vector<int>& nums, int target)
    {
        int left = 0, right = nums.size() - 1;
        while(left < right)
        {
            int mid = left + (right - left) / 2;
            if(nums[mid] < target)
                left = mid + 1;
            else
                right = mid;
        }
        if(nums[right] != target)
            return -1;
        return right;
    }

    // 查找区间的右端点
    int findRight(vector<int>& nums, int target)
    {
        int left = 0, right = nums.size() - 1;
        while(left < right)
        {
            int mid = left + (right - left + 1) / 2;
            if(nums[mid] > target)
                right = mid - 1;
            else
                left = mid;
        }
        if(nums[left] != target)
            return -1;
        return left;
    }
};

本文标签： 二分查找模板题在排序数组中查找元素的第一个和最后一个位置

版权声明：本文标题：【二分查找】模板题：在排序数组中查找元素的第一个和最后一个位置 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.betaflare.com/biancheng/1748212692a2827104.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。