Bisections solution, C++, 12ms, easy to understand


  • -1
    X

    First find the target value if any, and then keep extending the interval while possible, by recursively applying bisections search both to the left and right intervals from the target value initial location.

    class Solution {
    public:
        vector<int> searchRange(vector<int>& nums, int target) {
            vector<int> result{-1, -1};
            if(nums.empty() || target < nums.front() || target > nums.back()) return result;
            searchRangeRecursive(nums, 0, nums.size() - 1, target, result);
            return result;
        }
        
        void searchRangeRecursive(const vector<int>& nums, int start, int end, int target, vector<int>& result)
        {
            int start1 = start, end1 = end;
            while(start1 <= end1)
            {
                int mid = start1 + (end1 - start1)/2;
                if(target < nums[mid]) end1 = mid - 1;
                else if(target > nums[mid]) start1 = mid + 1;
                else
                {
                    result[0] = result[0] == -1 ? mid : min(result[0], mid);
                    result[1] = max(result[1], mid);
                    searchRangeRecursive(nums, start1, mid - 1, target, result);
                    searchRangeRecursive(nums, mid + 1, end1, target, result);
                    break;
                }
            }
        }
    };

Log in to reply
 

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