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]