http://oj.leetcode.com/problems/search-for-a-range/
要求复杂度为O(lgn),用二分查找的思想。
#include <iostream> #include <vector> using namespace std; class Solution { public: void fun(int* A,int start,int end,int target,vector<int> &ans) { if(start>end || ( start == end && A[start]!= target )) { ans.push_back(-1); ans.push_back(-1); return; } if(start == end && A[start] == target)//只有一个元素了 { ans.push_back(start); return; } if(A[start] == target && target ==A[end]) { ans.push_back(start); ans.push_back(end); return; } int middle = (start + end)/2; if(A[middle]<target) fun(A,middle+1,end,target,ans); else if(A[middle]>target) fun(A,start,middle-1,target,ans); else { ans.push_back(middle); return; } return; } vector<int> searchRange(int A[], int n, int target) { vector<int> ans; if(n == 0) return ans; fun(A,0,n-1,target,ans); int small,large; if(ans[0] == -1) //肯定没找到 { ans.clear(); ans.push_back(-1); ans.push_back(-1); return ans; } if(ans.size()==1) //ans中只有一个元素 small = large = ans[0]; if(ans.size() == 2) { small = ans[0]; large = ans[1]; } while(small>=0 && A[small] == target) //往左边扩展 small--; while(large<=n-1 && A[large] == target) //往右边扩展 large++; if(small == -1 || A[small]!=target) //考虑上面while循环的退出条件 small++; if(large== n || A[large]!=target) large--; ans.resize(2); //可能ans的size是1 ans[0] = small; //将扩展后的再赋值回来 ans[1] = large; return ans; } }; int main() { Solution myS; int A[] = {0,0,2,3,4,4,4,5}; vector<int> ans = myS.searchRange(A,8,0); return 0; }