文章目录
- 题目链接：
- 题目描述：
- 解法
- C++ 算法代码：
- 图解
- 总结模板
题目链接：
Leetcode 34.在排序数组中查找元素的第一个和最后一个位置
题目描述：
解法
暴力解法：
从前往后遍历数组，找到所有符合条件的位置，得到开始和结束位置。
朴素二分：
设置左右指针，和中点，然后把中间值和
target作比较，分情况讨论。但是这题这么做的话，时间复杂度会比较大。
二段性:
- 查找区间的左端点
细节处理：
循环条件
left<=right X
left<right √下面就为什么不可以用
<=要用<展开讲解分为
3种情况：t在left和right中间，t在left，t在right
t在left和right中间的情况：
所以，left=right的时候，就是最终结果，无需判断
t在left的情况：
此时，right向左移动，直到left=right=t，这个时候返回t的下标
如果t比left处的值还小，那么返回[-1,-1]
t在right的情况：
此时，left向右移动，直到left=right=t，这个时候返回t的下标
如果t比right处的值还大，那么返回[-1,-1]
注意：当满足第一个条件的时候，left=right=t，这个时候继续求中间值就陷入死循环了。
所以不可以写<=，要写<。
求中点的操作
有两种形式：
left+(right-left)/2
left+(right-left+1)/2
这么写只对偶数情况由影响：
left+(right-left)/2 | left+(right-left+1)/2 |
|---|---|
 |  |
表面上看起来好像差不多，但是如果只有两个的话：
按照left+(right-left+1)/2的话，mid在如图所示的位置：
若此时，x<t -> left=mid+1=x+1，left>right程序结束
若此时，x>=t -> right=mid=x，right原地不动，进入死循环。
按照left+(right-left)/2的话，mid在如图所示的位置：
若此时，x<t -> left=mid+1=x+1，left=right程序结束。
若此时，x>=t -> right=mid=x，left=right程序结束。
- 查找区间的右端点
求中点的情况，按照left+(right-left+1)/2，不然会死循环。
C++ 算法代码：
class Solution
{public:vector<int> searchRange(vector<int>& nums, int target) {// 处理边界情况if(nums.size() == 0) return {-1, -1};int begin = 0;// 1. 二分左端点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[left] != target) return {-1, -1};else begin = left; // 标记一下左端点// 2. 二分右端点left = 0, right = nums.size() - 1;while(left < right){int mid = left + (right - left + 1) / 2;if(nums[mid] <= target) left = mid;else right = mid - 1;}return {begin, right};}
};
图解
例如：[1, 2, 3, 3, 3, 4, 5]，t=3
经过第一个while(left < right)循环，找到左端点，也就是left=right的时候。得到左端点下标为2
经过第二个while(left < right)循环，找到右端点，也就是left=right的时候。得到右端点下标为4
返回[2,4]
总结模板
查找区间左端点的模板
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(......) left = mid;else right = mid - 1;
}
