大家好，又见面了，我是全栈君，今天给大家准备了Idea注册码。
问题叙述性说明：
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 ofO(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].
基本思路：
此题能够用二分查找法解决。
假设数组中没有target，能够在O（lgn）时间完毕。
假设数组中有target，当发现target后，对前后的内容继续用二分法 查找这种位置pos 。
- 前面的pos须要满足 A[pos] < target && A[pos+1] == target. pos+1即是開始位置。
- 后面的pos须要满足 A[pos] > target && A[pos-1] == target . pos-1是结束位置。
代码：
vector<int> searchRange(int A[], int n, int target) { //C++
vector<int> result(2);
int low = 0, high = n-1;
int mid, begin = -1, end = -1;
while(low <= high)
{
mid = (low+high)/2;
if(A[mid] > target)
high = mid - 1;
else if(A[mid] < target)
low = mid + 1;
else
{
begin = mid;
end = mid;
//get begin
if(low <= begin -1){
while((low <= begin-1) && !(A[low]<target && A[low+1] == target) )
{
mid = (low + begin-1)/2;
if(A[mid] < target)
low = mid+1;
else begin = mid;
}
if(A[low]<target && A[low+1] == target)
begin = low+1;
}
//get end
if(high >= end+1){
while((high >= end+1) &&!(A[high]>target && A[high-1] == target))
{
mid = (high + end +1)/2;
if(A[mid] > target)
high = mid - 1;
else end = mid;
}
if(A[high]>target && A[high-1] == target)
end = high - 1;
}
break;
}
}
result[0] = begin;
result[1] = end;
return result;
}
版权声明：本文博主原创文章，博客，未经同意不得转载。
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/116862.html原文链接：https://javaforall.net
