Problem statement

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

Solution

Use binary search with adaptation twice: once to find the left place and once to find the right place. I understand that goal is to write binary search from scratch if you are on the interview, but here is solution, using already existing bisect library in python. The idea is to use bisect (which is also bisect_right) and bisect_left to get the range of numbers: first one will return index before all repetitions of target and the second one: after. So, if these two indexes are equal, it means that we did not found this element, so we return [-1, -1]. If we found, we return [l, r - 1].

Complexity

Time complexity is O(log n), space is O(1).

Code

from bisect import bisect, bisect_left

class Solution:
    def searchRange(self, nums, target):
        l = bisect_left(nums,target)
        r = bisect(nums,target)
        return [-1, -1] if l == r else [l, r - 1]