【二分查找】模板题：在排序数组中查找元素的第一个和最后一个位置
文章目录
- 34. 在排序数组中查找元素的第一个和最后一个位置
- 解题思路
- 1、寻找左边界思路
- 2、寻找右边界思路
- 💥 查找左边界和右边界的模板
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] <= 109nums是一个非递减数组-109 <= target <= 109
解题思路
这道题算是找区间的左右端点的模板题，但是细节非常的多，我们必须要搞清楚，而不是去背模板，虽说模板代码很少，但是一定要理解！这道题用的还是二分思想，就是根据数据的性质，在某种判断条件下将区间一分为二，然后舍去其中一个区间，然后再另一个区间内查找；
如果我们想一次性找到左右边界，那么是非常难的，所以我们干脆拆开求左右区间，这样子省事多了！
为了方便叙述，下面统一用 target 表示该元素， resLeft 表示左边界， resRight 表示右边界。
1、寻找左边界思路
我们可以将数组划分为下面两个区间：
左区间
[left, resLeft - 1]区间都是小于target的右区间（包括左边界）
[resLeft, right]都是大于等于target的
因此对于 mid 来说，我们可以分为下面的两种情况来讨论：
-
当
mid落在[left, resLeft - 1]区间时，说明该区间元素都是小于target的，此时[left, mid]区间是可以舍弃的，所以left = mid + 1。
-
当
mid落在[resLeft, right]区间时，因为有可能nums[mid] > target，所以 不能直接返回结果。并且我们也 不能直接让right = mid - 1，因为万一mid就是最左端点的话，我们让right跳过去，那不就是错过了吗（这和我们的条件判断有关系），对不对，所以对于该情况我们采用的方式right = mid。
接下来就是处理细节问题：
终止循环条件：必须是
left < right，而不能是left ≤ right
要处理这个问题的话，我们需要结合双指针移动情况来看看是否能成立。当
left == right的时候，并且还一直让nums[mid] ≥ target成立的话，此时就会 陷入死循环，如下图所示，所以我们不能让left等于right，这是根据我们双指针的移动来的，不一定每种解法都是不能等于的，所以不能背题，要理解！
求中点的操作：必须是
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也就不会动，就导致了 死循环！
总结上述的细节，就是两点：
- 终止循环条件：
left < right - 求中点操作：
left + (right - left) / 2
2、寻找右边界思路
右边界其实就是左边界相反过来啦，懂了左边界的求法，右边界自然就懂了，只不过它们之间还是有细节之分的，主要体现在 求中点操作！
我们可以将数组划分为下面两个区间：
- 左区间（包括右边界）
[left, resLeft]区间都是小于等于target的- 右区间
[resLeft + 1, right]都是大于target的
因此对于 mid 来说，我们可以分为下面的两种情况来讨论：
- 当
mid落在[resLeft + 1, right]区间时，说明该区间元素都是大于target的，此时[mid, right]区间是可以舍弃的，所以right = mid-1。 - 当
mid落在[left, resLeft]区间时，因为有可能nums[mid] < target，所以 不能直接返回结果。并且我们也 不能直接让left= mid + 1，因为万一mid就是最右端点的话，我们让left跳过去，那就是错过了，所以对于该情况我们采用的方式left = mid。
接下来就是处理细节问题：
- 终止循环条件：必须是
left < right，而不能是left ≤ right
- 这个和处理左边界是一模一样的，具体的可以参考上面讲左边界求法中的细节处理，那里有讲为什么不能
left == right。- 求中点的操作：必须是
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就不动，就直接 死循环 了！
总结上述的细节，就是两点：
- 终止循环条件：
left < right - 求中点操作：
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;elseright = 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;elseleft = 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;elseright = mid;
}// 求右边界模板
while(left < right)
{int mid = left + (right - left + 1) / 2;if(……)right = mid - 1;elseleft = mid;
}