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

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

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

解题思路

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

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

​ 为了方便叙述，下面统一用 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

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

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;
    }
};

💥 查找左边界和右边界的模板

​ 需要注意的是，拿求左边界来说，然后 left 已经到达数组的末尾了还找不到 target 的话，此时 left 是停留在数组末尾的，如果有些题目需要做判断（比如说 35. 搜索插入位置 这道题），那么就得另行看看题目要求！

​ 而求右边界无非就是找不到 target 的话最后会停留在数组开头！

// 求左边界模板
while(left < right)
{
    int mid = left + (right - left) / 2;
    if(……)
        left = mid + 1;
    else
        right = mid;
}

// 求右边界模板
while(left < right)
{
    int mid = left + (right - left + 1) / 2;
    if(……)
        right = mid - 1;
    else
        left = mid;
}