C++ binary search solution (lower_bound implementation).


  • 21
    C
    vector<int> searchRange(vector<int>& nums, int target) {
        int idx1 = lower_bound(nums, target);
        int idx2 = lower_bound(nums, target+1)-1;
        if (idx1 < nums.size() && nums[idx1] == target)
            return {idx1, idx2};
        else
            return {-1, -1};
    }
    
    int lower_bound(vector<int>& nums, int target) {
        int l = 0, r = nums.size()-1;
        while (l <= r) {
            int mid = (r-l)/2+l;
            if (nums[mid] < target)
                l = mid+1;
            else
                r = mid-1;
        }
        return l;
    }

  • 0

    It is smart to avoid repeating the code by find the end of the range through reusing lower_bound. Simply find the starting index of next number and decrease it by 1.


  • 0
    T

    @caikehe great job! much tight and clean than mine

    Here is my solution, I used a bit slower way but it works.

    Step1. Binary search for the target
    Step2. Search towards left and right

    class Solution {
    public:
        vector<int> searchRange(vector<int>& nums, int target) {
            int left_binary = 0;
            int right_binary = nums.size() - 1;
            int mid;
            int start = -1; //initailize as -1 
            int end = -1;
            vector<int> result;
            
            //Step1. Binary search for the target
            while(left_binary <= right_binary)
            {
                mid = (left_binary + right_binary) / 2;
                if(nums[mid] == target)
                {
                    start = end = mid; //record the index
                }
                if(nums[mid] > target){right_binary = mid - 1;}
                else{left_binary = mid + 1;}
            }
            
            //Step2. search towards left and right
            while(start > 0 && nums[start - 1] == target){ --start;}
            while(end < nums.size() - 1 && nums[end + 1] == target){ ++end;} 
            
            result.push_back(start);
            result.push_back(end);
            
            return result;
          
        }
    
    };
    

Log in to reply
 

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