Sharing my C++ solution using two binary searches


  • 0
    T
    class Solution {
    private:
        int binarySearch1(vector<int>& nums, int target, int left, int right)
        {
            if(left>right)
                return -1;
            
            int middle = (left+right)/2;
            if(nums[middle]==target)
            {
                int temp = binarySearch1(nums, target, left, middle-1);
                if(temp>=0)
                    return temp;
                else
                    return middle;
            }
            else if(nums[middle]<target)
                return binarySearch1(nums, target, middle+1, right);
            else
                return binarySearch1(nums, target, left, middle-1);
        }
        
        int binarySearch2(vector<int>& nums, int target, int left, int right)
        {
            if(left>right)
                return -1;
            
            int middle = (left+right)/2;
            if(nums[middle]==target)
            {
                int temp = binarySearch2(nums, target, middle+1, right);
                if(temp>=0)
                    return temp;
                else
                    return middle;
            }
            else if(nums[middle]<target)
                return binarySearch2(nums, target, middle+1, right);
            else
                return binarySearch2(nums, target, left, middle-1);
        }
        
    public:
        vector<int> searchRange(vector<int>& nums, int target) {
            vector<int> result(2);
            result[0] = binarySearch1(nums, target, 0, nums.size()-1);
            result[1] = binarySearch2(nums, target, 0, nums.size()-1);
            
            return result;
        }
    };

Log in to reply
 

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