34. Find First and Last Position of Element in Sorted Array

Solution 1: Recursive Binary Search

Time Complexity: O(log(N))
Space Complexity: O(log(N)) // Recursive call stack

Solution 2: Iterative

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        ans = [-1, -1]
        n = len(nums)
        if n == 0:
            return ans
        
        # Find the 1st position of target
        lft, rht = 0, n - 1
        firstPos = -1
        while lft <= rht:
            mid = lft + (rht - lft) // 2
            if nums[mid] == target:
                firstPos = mid # keep updating the pos
                rht = mid - 1  # Check the left range
            elif nums[mid] > target:
                rht = mid - 1
            elif nums[mid] < target:
                lft = mid + 1
        ans[0] = firstPos
        
        # Find the 2nd position of target
        rht = n - 1
        lastPos = -1
        while lft <= rht:
            mid = lft + (rht - lft) // 2
            if nums[mid] == target:
                lastPos = mid  # keep updating the pos
                lft = mid + 1  # Check the right range
            elif nums[mid] > target:
                rht = mid - 1
            elif nums[mid] < target:
                lft = mid + 1
        ans[1] = lastPos
        
        return ans

Time Complexity: O(log(N))
Space Complexity: O(1)

Reference

https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/discuss/14699/Clean-iterative-solution-with-two-binary-searches-(with-explanation)