[LeetCode] Search for a Range
文章目录
Search for a Range
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].
For example, Given [5, 7, 7, 8, 8, 10] and target value 8, return [3, 4].
Binary Search
Time Complexity
O(logn)
Space Complexity
O(1)
思路
Do two binary search, first bs to find the first position, second bs to find the second position. If there is no target or only one target, return {-1, -1}. Remember when do the second binary search, make start = 0, end = nums.length -1 again.
代码
public int[] searchRange(int[] nums, int target) {
if(nums == null || nums.length == 0){
return new int[]{-1,-1};
}
int[] res = new int[2];
int start = 0, end = nums.length - 1, mid;
//find the first position
while(start + 1 < end){
mid = start + (end - start)/2;
if(nums[mid] >= target){
end = mid;
}else{
start = mid;
}
}
if(nums[start] == target){
res[0] = start;
}else if(nums[end] == target){
res[0] = end;
}else{
res[0] = -1;
res[1] = -1;
return res;
}
start = 0;
end = nums.length - 1;
//find the last position
while(start + 1 < end){
mid = start + (end - start)/2;
if(nums[mid] > target){
end = mid;
}else{
start = mid;
}
}
if(nums[end] == target){
res[1] = end;
}else if(nums[start] == target){
res[1] = start;
}else{
res[0] = -1;
res[1] = -1;
return res;
}
return res;
}

评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论