题解
用了两次二分，分别计算第一个>=target的元素位置和第一个>target的元素位置。闭区间二分，[l,r]是未知的，保证每次答案都在[l,r]中，定义清楚nums[l-1]和nums[r+1]和target的关系。因为是while(l < r)，所以到l == r时跳出循环，分析l == r时什么才是答案，处理好边界。
class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
vector<int> ans;
if(nums.size()==0)
{
ans.push_back(-1);
ans.push_back(-1);
return ans;
}
int left = 0, right = nums.size()-1;
// 计算第一个>=target的元素位置. [l,r] unknown, nums[l-1]<target, nums[r+1]>=target
while(left < right)
{
int mid = (left + right) / 2;
if(nums[mid] < target) left = mid + 1;
else right = mid;
}
int x1 = right; //第一个>=target的元素位置
if(nums[x1] != target)
{
ans.push_back(-1);
ans.push_back(-1);
return ans;
}
left = 0, right = nums.size()-1;
// 计算第一个>target的元素位置. [l,r] unknown, nums[l-1]<=target, nums[r+1]>target
while(left < right)
{
int mid = (left + right) / 2;
if(nums[mid] <= target) left = mid + 1;
else right = mid;
}
int x2 = nums[left] == target ? left+1 : left; //第一个>target的元素位置
ans.push_back(x1);
ans.push_back(x2-1);
return ans;
}
};
// 0 1 2 3 4 5
// 5 8 8 8 8 10
// L m R
// L m R
// L R
//
- Leetcode Position Element Sorted Arrayleetcode position element sorted duplicates remove sorted array sorted merge array sorted array sort differences leetcode absolute sorted cpp-array-element-count leetcode sorted merge lists frog-position-after-t-seconds leetcode problems cpp-array-element-count element array count 数组leetcode squares sorted