Leetcode 34 Solution
Leetcode Question Link
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 + 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
N is the size of the array:
- Time complexity:
- Space complexity:
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]