LintCode (61) Search for range

Given a sorted array of n integers, find the starting and ending position of a given target value.

If the target is not found in the array, return [-1, -1].

Have you met this question in a real interview? 

Yes

Example

Given [5, 7, 7, 8, 8, 10] and target value 8, return [3, 4].

Challenge

O(log n) time.

这个题很羞愧，其实是做过好多次，每次都忘记考虑输入为空的情况。。。。

1. 当输入为空，返回default

2. 套用模板， 搜索结束后，判断beg是不是，或者end是不是，都不是返回default, 因为beg肯定是第一个出现的值的位置，否则end就是只有一个这个数字了

3. 然后向后搜索。 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39

class Solution { /** *@param A : an integer sorted array *@param target : an integer to be inserted *return : a list of length 2, [index1, index2] */ public: vector<int> searchRange(vector<int> &A, int target) { // write your code here vector<int> res(2,-1); if (A.empty()) return res; int beg=0; int end=A.size()-1; while(beg+1<end){ int mid=beg+(end-beg)/2; if (A[mid]==target) end=mid; else if (A[mid]<target) beg=mid; else end=mid; } if (A[beg]==target){ res[0]=beg; } else if (A[end]==target){ res[0]=end; } else{ return res; } int ind=res[0]; while(ind<A.size()-1 && A[ind]==A[ind+1]){ ind++; } res[1]=ind; return res; } };