9-11 lines O(log n)


  • 49

    Solution 1 : Divide and Conquer with early breaks : 56 ms

    The O(log n) time isn't quite obvious, so I'll explain it below. Or you can take the challenge and prove it yourself :-)

    def searchRange(self, nums, target):
        def search(lo, hi):
            if nums[lo] == target == nums[hi]:
                return [lo, hi]
            if nums[lo] <= target <= nums[hi]:
                mid = (lo + hi) / 2
                l, r = search(lo, mid), search(mid+1, hi)
                return max(l, r) if -1 in l+r else [l[0], r[1]]
            return [-1, -1]
        return search(0, len(nums)-1)
    

    The search helper function returns an index range just like the requested searchRange function, but only searches in nums[lo..hi]. It first compares the end points and immediately returns [lo, hi] if that whole part of nums is full of target, and immediately returns [-1, -1] if target is outside the range. The interesting case is when target can be in the range but doesn't fill it completely.

    In that case, we split the range in left and right half, solve them recursively, and combine their results appropriately. Why doesn't this explode exponentially? Well, let's call the numbers in the left half A, ..., B and the numbers in the right half C, ..., D. Now if one of them immediately return their [lo, hi] or [-1, -1], then this doesn't explode. And if neither immediately returns, that means we have A <= target <= B and C <= target <= D. And since nums is sorted, we actually have target <= B <= C <= target, so B = C = target. The left half thus ends with target and the right half starts with it. I highlight that because it's important. Now consider what happens further. The left half gets halved again. Call the middle elements a and b, so the left half is A, ..., a, b, ..., B. Then a <= target and:

    • If a < target, then the call analyzing A, ..., a immediately returns [-1, -1] and we only look further into b, ..., B which is again a part that ends with target.
    • If a == target, then a = b = ... = B = target and thus the call analyzing b, ..., B immediately returns its [lo, hi] and we only look further into A, ..., a which is again a part that ends with target.

    Same for the right half C, ..., D. So in the beginning of the search, as long as target is only in at most one of the two halves (so the other immediately stops), we have a single path. And if we ever come across the case where target is in both halves, then we split into two paths, but then each of those remains a single path. And both paths are only O(log n) long, so we have overall runtime O(log n).

    This is btw based on us917's solution.


    Solution 2 : Two binary searches : 56 ms

    def searchRange(self, nums, target):
        def search(n):
            lo, hi = 0, len(nums)
            while lo < hi:
                mid = (lo + hi) / 2
                if nums[mid] >= n:
                    hi = mid
                else:
                    lo = mid + 1
            return lo
        lo = search(target)
        return [lo, search(target+1)-1] if target in nums[lo:lo+1] else [-1, -1]
    

    Here, my helper function is a simple binary search, telling me the first index where I could insert a number n into nums to keep it sorted. Thus, if nums contains target, I can find the first occurrence with search(target). I do that, and if target isn't actually there, then I return [-1, -1]. Otherwise, I ask search(target+1), which tells me the first index where I could insert target+1, which of course is one index behind the last index containing target, so all I have left to do is subtract 1.


    Solution 3 : Two binary searches, using the library

    Binary search is so good and common that many languages have it in their standard library and you just need to figure out how to apply it to the problem at hand.

    Python:

    def searchRange(self, nums, target):
        lo = bisect.bisect_left(nums, target)
        return [lo, bisect.bisect(nums, target)-1] if target in nums[lo:lo+1] else [-1, -1]
    

    C++:

    vector<int> searchRange(vector<int>& nums, int target) {
        auto bounds = equal_range(nums.begin(), nums.end(), target);
        if (bounds.first == bounds.second)
            return {-1, -1};
        return {bounds.first - nums.begin(), bounds.second - nums.begin() - 1};
    }
    

    Or:

    vector<int> searchRange(vector<int>& nums, int target) {
        int lo = lower_bound(nums.begin(), nums.end(), target) - nums.begin();
        if (lo == nums.size() || nums[lo] != target)
            return {-1, -1};
        int hi = upper_bound(nums.begin(), nums.end(), target) - nums.begin() - 1;
        return {lo, hi};
    }
    

    Java:

    Well, Java decided to be annoying and offer Arrays.binSearch but with "If the array contains multiple elements with the specified value, there is no guarantee which one will be found". So it's useless for us. I'm not good at Java, though, so maybe I'm overlooking a way to still make it work. If you manage to do so, please let me know.


  • 6

    I really like the first Divide and Conquer solution and the proof of its running time. I rewrite it in C++ and it achieves the fastest running time (12 ms) among the C++ codes :-)

    class Solution {
    public:
        vector<int> searchRange(vector<int>& nums, int target) {
            int n = nums.size();
            return search(nums, 0, n - 1, target);
        }
    private: 
        vector<int> search(vector<int>& nums, int l, int r, int target) {
            if (nums[l] == target && nums[r] == target) return {l, r};
            if (nums[l] <= target && target <= nums[r]) {
                int mid = l + ((r - l) >> 1);
                vector<int> left = search(nums, l, mid, target);
                vector<int> right = search(nums, mid  +1, r, target);
                if (left[0] == -1) return right;
                if (right[0] == -1) return left;
                return {left[0], right[1]};
            }
            return {-1, -1};
        }
    };
    

    BTW, thanks to the great C++ 11 features of vector initialization using {}, which saves a lot of codes :-)

    Update: an absolutely high-quality post. I read through all the solutions and learn a lot from them, the algorithm, the proof, and the details of the codes. Thanks a lot!


  • 0

    It actually took me some time to discover the target in nums[lo:lo+1] in Solution 2 :-)


  • 4
    M

    Thanks for sharing and this is my JAVA version for divide and conquer method:

    public int[] searchRange(int[] nums, int target) {
        return helper(nums, target, 0, nums.length - 1);
    }
    private int[] helper(int[] nums, int target, int lo, int hi) {
        if (nums[lo] == target && nums[hi] == target) return new int[]{lo, hi};
        if (nums[lo] <= target && nums[hi] >= target) {
            int mid = lo + (hi - lo) / 2;
            int[] left = helper(nums, target, lo, mid);
            int[] right = helper(nums, target, mid + 1, hi);
            if (left[0] == -1) return right;
            if (right[0] == -1) return left;
            return new int[]{left[0], right[1]};
        }
        return new int[]{-1, -1};
    }
    

  • 0
    G

    Three solutions, and in different languages... Bravo!

    Could you explain this line please - return max(l, r) if -1 in l+r else [l[0], r[1]]?


  • 0

    @gudnm What part of it is unclear? It's all pretty basic stuff...


  • 0
    G

    if -1 in l+r doesn't make sense to me... thanks!


  • 0

    l and r are the results for the left and right half, so that just tests whether one of them is doesn't contain the target (e.g., if l+r is [3, 5, -1, -1]).


  • 0
    B

    I saw a lot of your brilliant solutions.
    I have a question about the coding style in a lot of your code.
    What's the benefit of having function inside function in comparison with write another function at same level?
    Just like the search and searchRange inthis question.

    It seems like the nums and target is shared between search and searchRange?

    def searchRange(self, nums, target):
        def search(lo, hi):
            if nums[lo] == target == nums[hi]:
                return [lo, hi]
            if nums[lo] <= target <= nums[hi]:
                mid = (lo + hi) / 2
                l, r = search(lo, mid), search(mid+1, hi)
                return max(l, r) if -1 in l+r else [l[0], r[1]]
            return [-1, -1]
        return search(0, len(nums)-1)
    

  • 0
    R

    Hello, I have a question. The function in List is O(N) , when I use it in my code like this:
    if target not in nums:
    return [-1,-1]
    else:
    return [bisect.bisect_left(nums,target),bisect.bisect_right(nums,target)-1]
    it still accepted......why?


  • 1
    D

    thanks for sharing!!!
    the C++ code can't pass the testcase:
    [-1]
    0
    I think it needs to consider the case that 'target' bigger than all integers in 'array'
    so the following code is better:

    class Solution {
    public:
        vector<int> searchRange(vector<int>& nums, int target) {
            if(nums.empty()) return vector<int>{-1,-1};
            auto bounds = equal_range(nums.begin(), nums.end(), target);
            return *bounds.first != target ||  bounds.first-nums.begin()>=nums.size() ? vector<int> {-1, -1} :
                                         vector<int> {bounds.first - nums.begin(),
                                                      bounds.second - nums.begin() - 1};
    /*        if(nums.empty()) return vector<int>{-1,-1};
            auto low = lower_bound(nums.begin(),nums.end(),target);
            if(*low == target && low-nums.begin()<nums.size())
                return vector<int>{low-nums.begin(),upper_bound(nums.begin(),nums.end(),target)-nums.begin()-1};
            return vector<int>{-1,-1};
    */    }
    };

  • 0
    D

    @jianchao.li.fighter very nice, thank you


  • 0

    @Dexter_GUO Oh wow, what was I thinking? I shouldn't blindly access *bounds.first at all, as that's undefined/dangerous if bounds.first is nums.end(). You shouldn't, either. Thanks, I fixed my C++ solutions. And removed the unnecessary "vector<int>" in the return values while I was at it.


  • 1

    My naive approach.

    public int[] searchRange(int[] nums, int target) {
            if (nums.length == 0) return new int [] { -1, -1 };
            int low = 0, high = nums.length - 1;
            while (low + 1 < high) {
                int mid = (low + high) >>> 1;
                if (nums [mid] >= target) high = mid;
                else low = mid;
            }
            int first = (nums [low] == target) ? low : (nums [high] == target ? high : -1);
            low = 0; high = nums.length - 1;
            while (low + 1 < high) {
                int mid = (low + high) >>> 1;
                if (nums [mid] > target) high = mid;
                else low = mid;
            }
            int last = (nums [high] == target) ? high : (nums [low] == target ? low : -1);
            return new int [] { first, last };
    }
    

Log in to reply
 

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