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].
Hide Tags
这道是变形的二分搜索，写的有点冗余，没有很好的合并在一起。
方法是先二分搜索到 其中一个target， 然后分别二分搜索边界。
#include <vector>
#include <iostream>
using namespace std; class Solution {
public:
vector<int> searchRange(int A[], int n, int target) {
vector<int > ret(,-);
if(n<) return ret;
int mid = helpFun(A,,n-,target);
if(mid !=-){
ret[]=helpLeft(A,,mid,target);
ret[]=helpRight(A,mid,n-,target);
}
return ret;
} int helpLeft(int *a,int lft, int rgt, int & tar)
{
if(a[lft]==tar) return lft;
if(lft+==rgt) return rgt;
int mid = (lft+rgt)/;
if(a[mid]==tar) return helpLeft(a,lft,mid,tar);
else return helpLeft(a,mid,rgt,tar);
} int helpRight(int *a,int lft, int rgt, int & tar)
{
if(a[rgt]==tar) return rgt;
if(lft+==rgt) return lft;
int mid = (lft+rgt)/;
if(a[mid]==tar) return helpRight(a,mid,rgt,tar);
else return helpRight(a,lft,mid,tar);
} int helpFun(int *a,int lft, int rgt, int & tar)
{
if(lft>rgt) return -;
if(lft == rgt){
if(tar==a[lft]) return lft;
return -;
}
if(lft + == rgt){
if(a[lft]==tar) return lft;
if(a[rgt]==tar) return rgt;
return -;
}
int mid = (lft+rgt)/;
if(a[mid]==tar) return mid;
if(a[mid]<tar) return helpFun(a,mid+,rgt,tar);
else return helpFun(a,lft,mid-,tar);
}
}; int main()
{
int A[]={, , , , , };
Solution sol;
vector<int > ret = sol.searchRange(A,sizeof(A)/sizeof(int),);
cout<<ret[]<<ret[]<<endl;
return ;
}
附件是一份集成的比较好的，思路是一样：
vector<int> searchRange(int a[], int n, int target) {
vector<int> result(,-);
int left = INT_MAX;
int right = INT_MIN;
binSearch(a, , n-, n, target, left, right);
if (left != INT_MAX && right != INT_MIN) {
result[] = left;
result[] = right;
}
return result;
}
void binSearch(int a[], int l ,int h, int n, int target, int& left, int& right) {
if (l > h) return;
int m = (l+h)/;
if (a[m] > target) {
binSearch(a,l,m-,n,target, left, right);
} else if (a[m] < target) {
binSearch(a,m+,h,n,target, left, right);
} else {
if (m < left) {
left = m;
if (m > && a[m-] == target) {
binSearch(a,l,m-,n,target,left,m);
}
}
if (m > right) {
right = m;
if (m < n- && a[m+] == target) {
binSearch(a,m+,h,n,target,m,right);
}
}
}
}