Lintcode: Search for a 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.

Tags Expand 

Binary Search Sorted Array Array

Thoughts:
With binary search, we can get the first element equal to target and first element larger than target.
So I binary search twice to get the range.
If I just use one binary search, I may take O(n) to get range in worst case.
Time: O(2logn) = O(logn)
Space: O (1)

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
        //even A is null, result will return -1, -1
        vector<int> result;
        int start = 0;
        int end = A.size() - 1;
        while(start <= end){
            int mid = (start + end) / 2;
            if(A[mid] < target) start = mid + 1;
            if(A[mid] >= target) end = mid - 1;
        }
        //if target is too small, start = 0, end = -1
        //if target is too large, start = A.size(), end = A.size() - 1;
        // if target is not in A, start point to first element more than target
        // if target is in A, start point to first element equal to target
        if(start < A.size() && A[start] == target) {
            result.push_back(start);
        }else{
            result.push_back(-1);
            result.push_back(-1);
            return result;
        }
        start = 0;
        end = A.size() - 1;
        while(start <= end){
            int mid = (start + end) / 2;
            if(A[mid] <= target) start = mid + 1;
            if(A[mid] > target) end = mid - 1;
        }
        //here, the target must exist in A, start points to the first element larger than target.
        //If no element larget than target, start point to A.size()
        //So start - 1 will be the last index of elements in A equals to target.
        result.push_back(start - 1);
        return result;
    }
};