Leetcode 34 -> Find First and Last Position of Element in Sorted Array

 We use the modified binary search here, when we find the element we don’t break our binary search, instead we keep on moving, One time towards left and another time towards the right to find the left most and right most index of our target. The below code illustrates the approach more clearly.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

class Solution:
    
    def bin_search(self,nums,target,lr):
        n = len(nums)
        low = 0
        high = n-1
        tfound = None
        while low<=high:
            mid = (low+high)//2
            if nums[mid] == target:
                tfound = mid
                if lr == "left":
                    high = mid-1
                else:
                    low = mid + 1
                # break
            elif target < nums[mid]:
                high = mid - 1
            else:
                low = mid + 1
        if tfound == None:
            tfound = -1
        return tfound
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        
        n = len(nums)
        
        lb = self.bin_search(nums,target,"left")
        ub = self.bin_search(nums,target,"right")
        return [lb,ub]

Popular Posts