C++ O(logn) binary-search, implemented myself...


  • 0
        vector<int> searchRange(vector<int>& nums, int target) {
            int n = nums.size();
            if(n == 0) return {-1,-1};
            
            int lower, upper;
            // BS
            int lo(0), hi(n-1);
            int mid = (lo + hi) / 2;
            while(lo <= hi){
                if(nums[mid] < target) lo = mid + 1;
                else hi = mid - 1;
                mid = (lo + hi) / 2;
            }
            lower = lo;
            // BS
            lo = 0, hi = n-1;
            mid = (lo + hi) / 2;
            while(lo <= hi){
                if(nums[mid] > target) hi = mid - 1;
                else lo = mid + 1;
                mid = (lo + hi) / 2;
            }
            upper = hi;
            
            if(lower > upper) return {-1,-1};
            return {lower, upper};
        }
    

    Then I realized it only needs 4 lines using STL...

        vector<int> searchRange(vector<int>& nums, int target) {
            int lo = lower_bound(nums.begin(), nums.end(), target) - nums.begin();
            int hi = upper_bound(nums.begin(), nums.end(), target) - nums.begin() - 1;
            if(lo > hi) return {-1,-1};
            return {lo, hi};
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.