Simple solution and explanation C++ O(log n)


  • 0
    A
    1. Find the target with binary search
    2. Find the rest forwards
    3. Find the rest backwards
    class Solution {
    public:
        vector<int> searchRange(vector<int>& nums, int target) {
            int index = recursiveFind(nums, 0, nums.size() - 1, target);
            if(index == -1) return vector<int>{-1, -1};
            int i = index, j = index;
            while(i >= 0 && nums[i] == target) i--;
            while(j < nums.size() && nums[j] == target) j++;
            return vector<int>{i+1, j-1};
        }
        int recursiveFind(vector<int>& nums, int start, int end, int target){
            if(start > end || nums.empty()) return -1;
            int mid = (start + end) / 2;
            if(nums[mid] == target) return mid;
            else if(nums[mid] < target) return recursivefind(nums, mid+1, end, target);
            else return recursivefind(nums, start, mid-1, target);
        }
    };
    

Log in to reply
 

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