[LeetCode] Search for a Range
Search for a Range
Given a sorted array of integers, 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].
For example,
Given [5, 7, 7, 8, 8, 10] and target value 8,
return [3, 4].
解题思路：
这道题的题意是找到排序数组中目标值的下标范围，这个数组可能会有相同的元素。
题目要求时间复杂度在O(logn)。3次二分查找。第一次找到一个值为target的下标k，第二次找到0~k中值为target的最小下标，第三次找到k~len-1中值为target的最大下标。每次的时间复杂度为O（logn）。
class Solution {
public:
vector searchRange(vector& nums, int target) {
vector result({-1, -1});
int start=0, end=nums.size()-1;
int middle;
//找到第一个
while(start<=end){
middle=(start+end)/2;
if(nums[middle]==target){
result[0]=result[1]=middle;
break;
}else if(nums[middle]>target){
end=middle-1;
}else{
start=middle+1;
}
}
if(result[0]!=-1){
//找到最小的那个下标
start=0;
end=result[0]-1;
while(start<=end){
middle=(start+end)/2;
if(nums[middle]==target){
end=middle-1;
result[0]=middle;
}else{
start=middle+1;
}
}
//找到最大的那个下标
start=result[1]+1;
end=nums.size()-1;
while(start<=end){
middle=(start+end)/2;
if(nums[middle]==target){
start=middle+1;
result[1]=middle;
}else{
end=middle-1;
}
}
}
return result;
}
};
二次刷题（2015-08-18）
class Solution {
public:
vector searchRange(vector& nums, int target) {
int len = nums.size();
vector result({-1, -1});
int start = 0, end = len - 1;
while(start <= end){
int middle = (start + end) / 2;
if(nums[middle] == target){
result[0] = result[1] = middle;
break;
}else if(nums[middle] < target){
start = middle + 1;
}else{
end = middle - 1;
}
}
if(result[0]>=0){
//找到左侧的
start = 0;
end = result[0]-1;
while(start<=end){
int middle = (start + end)/2;
if(nums[middle] == target){
result[0] = middle;
end = middle - 1;
}else{
start = middle + 1;
}
}
//找到右侧的
start = result[1] + 1;
end = len - 1;
while(start<=end){
int middle = (start + end) / 2;
if(nums[middle] == target){
result[1] = middle;
start = middle + 1;
}else{
end = middle - 1;
}
}
}
return result;
}
};
转载请注明： » [LeetCode] Search for a Range
<!--
-->
原文作者：；如有侵权，请联系管理员删除。
上一篇：
在国外，听网易音乐
下一篇：
svn被防火墙block
请登录后发表评论
登录
全部评论
