题目解析
34. 在排序数组中查找元素的第一个和最后一个位置
我们使用暴力方法进行算法演化,寻找一个数字的区间,我们可以顺序查找,记录最终结果
首先数组是有序的,所以使用二分法很好上手,但是我们就仅仅使用上一道题的二分方法,这里就仅仅只能够找到这个数组中的target,但是我们不能确保是否是端点
- 因此我们要使用两次二分,寻找左端点和右端点
- 先看代码,这里面有几个细节,看到代码说
算法讲解
class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
if(nums.size() == 0)return {-1, -1};
//本题就是寻找target的左端点 右端点
int left_ret = 0, right_ret = 0;
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,-1};
else left_ret = left;
//寻找右端点
right = nums.size() - 1;
while (left < right)
{
int mid = left + (right - left + 1) / 2;
if (nums[mid] <= target)left = mid;
else right = mid - 1;
}
right_ret = right;
return { left_ret, right_ret };
}
};