# Leetcode 34 Solution

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]
``````