C++12ms Easy to understand approach


  • 0
    Z

    // deploy binary search twice, looking for left and right bound respectively.
    // the trick is adding an element at the start and end of the vector.

    class Solution {

    vector<int> searchRange(vector<int>& nums, int target) {
        vector<int> def = {-1,-1};
        vector<int> vec;
        int idx;
        if (nums.empty())
            return def;
        
        nums.insert(nums.begin(), 0x3fffffff);
        nums.push_back(0x3fffffff);
        int size = nums.size();
        int left = helper(nums, target, 1, size-2, true);
        int right = helper(nums, target, 1, size-2, false);
        vec.push_back(left-1);
        vec.push_back(right-1);
        return vec;
    }
    
    int helper(vector<int>& nums, int target, int left, int right, bool findleft) {
        if (left > right)
            return 0;
        int mid = (left+right)/2;
        if (findleft && nums[mid]==target && nums[mid-1] != target)
            return mid;
        if (!findleft && nums[mid]==target && nums[mid+1] != target)
            return mid;
        if (nums[mid] == target && target == nums[mid-1]) {
            if (findleft)
                return helper(nums, target, left, mid-1, true);
        }
        if (nums[mid] == target && target == nums[mid+1]) {
            if (!findleft)
                return helper(nums, target, mid+1, right, false);
        }
        if (nums[mid] > target)
            return helper(nums, target, left, mid-1, findleft);
        if (nums[mid] < target)
            return helper(nums, target, mid+1, right, findleft);
        
    }
    

    };


Log in to reply
 

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