Leetcode 34 Solution

Leetcode Question Link

https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array

Thinking Process

This question can be transformed into a simpler one. If we can find the index of the first element greater than or equal to x, we can calculate the result for this question. Here’s how.

Let’s say that index is F(x), then we can calculate F(x) and F(x + 1) - 1. If nums[F(x)] != x, we know that x didn’t even show up in the array, so just return [-1, -1]. Otherwise, the range should be [F(x), F(x + 1) - 1]. Of course, you’ll need to handle the boundary case, because there is a chance that x is the largest element in the array.

Now the question becomes find the index of the first element greater than or equal to x, which is a basic binary search problem. As for how, check out this.

Time & Space Complexity

Assuming N is the size of the array:

• Time complexity: O(lg N)
• Space complexity: O(1)

Solution

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        if not nums:
            return [-1, -1]

        def bsearch(nums, target):
            l = 0
            r = len(nums) - 1

            while l < r:
                m = (l + r) // 2

                if nums[m] >= target:
                    r = m
                else:
                    l = m + 1

            return l

        lbound = bsearch(nums, target)
        rbound = bsearch(nums, target + 1)

        if nums[lbound] != target:
            return [-1, -1]

        if nums[rbound] > target:
            return [lbound, rbound - 1]
        else:
            return [lbound, rbound]