Algorithm

LintCode/Search For A Range

Problem Summary

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

Solution

We need to use binary search twice. The first is in range [0,…,N-1], and if we find a legal l, we ran the second binary search in range [l,..,N-1].

Be careful about how to calculate mid to prevent endless loop.

Code

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
40
41
42
43
44
45
class Solution {
public:
    /*
     * @param A: an integer sorted array
     * @param target: an integer to be inserted
     * @return: a list of length 2, [index1, index2]
     */
    vector<int> searchRange(vector<int> &A, int target) {
    	vector<int> ans;
        int n = A.size();
        int l = 0, r = n-1;
        while (l<r) {
        	int mid = l + ((r-l)>>1);
        	if (A[mid]==target)
        		r = mid;
        	else
        	if (A[mid]<target)
        		l = mid+1;
        	else
        		r = mid-1;
        }
        if (l>=n || A[l]!=target) {
        	ans.push_back(-1);
        	ans.push_back(-1);
        	return ans;
        }
        else
        	ans.push_back(l);
        r = n-1;
        while (l<r) {
        	int mid = l + ((r-l)>>1) + 1;
        	if (A[mid]==target)
        		l = mid;
        	else
        	if (A[mid]<target)
        		l = mid+1;
        	else
        		r = mid-1;
        }
        ans.push_back(r);
        return ans;
    }
};