34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣(LeetCode)
题目要求:时间复杂度为:O(logN),而且是有序数组,那一定就是二分法解决了
解法:二分查找
1.左端点
要找一个元素的第一次出现的位置的情况,我们可以把数组分为两个区间,如下:
因为如果mid 落在 <3的区间,可以直接让left = mid + 1,因为答案绝对不可能在 <3 的区间里。
1. mid < target left = mid + 1;
因为如果mid 落在 >=3的区间,就不可以让 right = mid - 1,因为此区间是 >= 3的,所以有可能mid就在此区间第一个 == 3的位置,如果更新right 为 mid - 1,那么就会跑到<3的区间,永远都找不到值。
2.mid >= target right = mid;
3.循环结束条件 while(left < right) 因为上面的逻辑 最后会走到 left == right 才会有最终答案
2.右端点
要找一个元素的最后一次出现的位置的情况,我们可以把数组分为两个区间,如下:
因为如果mid 落在 >3的区间,可以直接让right = mid - 1,因为答案绝对不可能在 >3 的区间里。
1. mid > target right = mid - 1;
因为如果mid 落在 <=3的区间,就不可以让 left = mid + 1,因为此区间是 <= 3的,所以有可能mid就在此区间最后一个 == 3的位置,如果更新left 为 mid + 1,那么就会跑到>3的区间,永远都找不到值。
2.mid <= target left = mid;
3.循环结束条件 while(left < right) 因为上面的逻辑 最后会走到 left == right 才会有最终答案
细节问题
1.数组中没有target的情况
直接先在开始判断 :如果 数组元素为0,返回 {-1,-1}
判断左端点的时候 最后left == right ,只需循环结束后,判断一下 != target 返回{-1,-1}即可.
2.不动问题
求左端点,如果用右边的 +1 公式求mid,那么最后剩两个元素的时候,如果命中 mid >= target的条件上,那么right不会动,程序陷入死循环, 所以 要用不+1的公式。
求右端点,如果用左边 不+1 公式求mid,那么最后剩两个元素的时候,如果命中 mid <= target的条件上,那么left不会动,程序陷入死循环, 所以 要用+1的公式。
class Solution {
public:vector<int> searchRange(vector<int>& nums, int target) {if(nums.size() == 0)return {-1,-1};vector<int> ret;int mid = 0;//1.寻找区间左端点int left = 0,right = nums.size()-1;while(left<right){mid = left + (right - left) /2;if(nums[mid] < target) left = mid + 1;else if(nums[mid] >= target)right = mid;}//走到这,left = right,找到左端点,但还需判断是不是 == targetif(nums[left] != target)return {-1,-1};elseret.push_back(left);//2.寻找区间右端点left = 0,right = nums.size()-1;while(left<right){mid = left + (right - left + 1) /2;if(nums[mid] <= target)left = mid;else if(nums[mid] > target)right = mid - 1;}//走到这,left = right,找到右端点ret.push_back(left);return ret;}
};