LeetCode 34 在排序数组中查找元素的第一个位置和最后一个位置 二分查找经典变种 值得一看

题目链接

思路：

1. 一个自然的想法是先二分查找然后分别往左右遍历，找到所求的位置。但这样的话，最优复杂度达不到进阶题目要求的情况。或许可以在面试的时候先这么说，引导面试官让你优化，然后惊艳面试官，哈哈哈~
2. 使用两次二分查找，分别查找满足要求的左右坐标值，具体的思路在代码注释中了。

网上一个优秀题解的情况分析：

AC代码：

class Solution {
    
public:int searchleft(vector<int> &nums, int target){
    //第一个小于target的数的坐标//不断取左半区间 然后返回右边界值//为什么res指示值为-2？ //因为在返回右边界的情况下是mid-1,可能取值为-1，因此res指示值不能取-1了int left = 0, right = nums.size() - 1, res = -2;while(left<=right){
    int mid = (left + right) / 2;// 注意细节 大于等于号 然后坐标减一//如果res的值不再更新 也就是不再进入到这个判断条件中//那么res坐标的值必然是小于target值的第一个坐标if(nums[mid]>=target){
     right = mid - 1;res = right;}else{
    left = mid + 1;}}return res; // res为-2说明数组中所有元素均小于target}int searchright(vector<int> & nums, int target){
    //第一个大于target的数的坐标//不断取右半区间，返回左边界int left = 0, right = nums.size() - 1, res = -2;while(left<=right){
    int mid = (left + right) / 2;if(nums[mid]<=target){
    left = mid + 1;res = left;}else{
    right = mid - 1;}}return res; //res为-2则代表所有元素均小于target}vector<int> searchRange(vector<int>& nums, int target) {
    int leftidx = searchleft(nums, target);int rightidx = searchright(nums, target);if(leftidx == -2 || rightidx == -2) return {
    -1, -1}; // 情况1// target的值在区间中if(rightidx - leftidx > 1){
     // 确保至少存在一个target值return {
    leftidx + 1, rightidx - 1}; // 情况3}else return {
    -1, -1}; // 情况2}
};