34. Search for a Range

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].

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        vector<int> res(2, -1);

        auto iter1 = lower_bound(nums, target);
        auto iter2 = upper_bound(nums, target);

        if(iter1 == iter2)
            return res;
        else{
            res[0] = iter1;
            res[1] = iter2 - 1;
        }
        return res;
    }
private:
    int lower_bound(vector<int> &arr, int key){
        int lb = -1, ub = arr.size();

        while(ub - lb > 1){
            int mid = (lb + ub) >>1;
            if(arr[mid] >= key){
                ub  = mid;
            }else{
                lb = mid;
            }
        }
        return ub;
    }
    int upper_bound(vector<int> &arr, int key){
        int lb = -1, ub = arr.size();

        while(ub - lb > 1){
            int mid = (lb + ub) >>1;
            if(arr[mid] > key){
                ub  = mid;
            }else{
                lb = mid;
            }
        }
        return ub;
    }
};