Description
Given an array of integers sorted in ascending order, find the starting and ending position of a given target value.
Your algorithm's runtime complexity must be in the order of O(log n).
If the target is not found in the array, return [-1, -1].
Example
For example,
Given [5, 7, 7, 8, 8, 10] and target value 8,
return [3, 4].思路
- 二分查找
- 两次二分，分别查找左边起点和右边终点
- 对应于代码中flag = 1,找左边；flag = 0, 找右边
代码
class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
vector<int> res;
int len = nums.size();
res.push_back(binarySearch(nums, len, target, 1));
res.push_back(binarySearch(nums, len, target, 0));
return res;
}
int binarySearch(vector<int>& nums, int len, int target, int flag){
int low = 0, high = len - 1;
int mid = 0;
while (low <= high){
mid = low + (high - low) / 2;
if (nums[mid] == target){
if (flag){
if (mid == low || mid - 1 >= low && nums[mid - 1] < nums[mid])
return mid;
else high = mid - 1;
}
else{
if (mid == high || mid + 1 <= high && nums[mid + 1] > nums[mid])
return mid;
else low = mid + 1;
}
}
else if (nums[mid] > target)
high = mid - 1;
else low = mid + 1;
}
return -1;
}
};内容来源于网络如有侵权请私信删除
- 还没有人评论，欢迎说说您的想法！
客服
