LC 0034 [M] Find First and Last Position of Element in Sorted Array - ALawliet/algorithms GitHub Wiki

arrow points to _most (< = leftmost, set l) (> = rightmost, set r)

to make it even fast, you can also pass the binary search left index into the binary search right to constrain the search space

function binary_search_leftmost(A, n, T):
    L := 0
    R := n
    while L < R:
        m := floor((L + R) / 2)
        if A[m] < T:
            L := m + 1
        else:
            R := m
    return L

function binary_search_rightmost(A, n, T):
    L := 0
    R := n
    while L < R:
        m := floor((L + R) / 2)
        if A[m] > T:
            R := m
        else:
            L := m + 1
    return R - 1

class Solution:
    def searchRange(self, A: List[int], T: int) -> List[int]:
        l = bisect_left(A, T)
        r = bisect_right(A, T, l) # passing l at the end is an optimization
        return [l, r-1] if l < r else [-1, -1]

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        def binarySearchLeft(A, T):
            n = len(A)
            l = 0
            r = n
            while l < r:
                m = (l + r) // 2
                if A[m] < T:
                    l = m + 1
                else:
                    r = m
            return l

        def binarySearchRight(A, T):
            n = len(A)
            l = 0
            r = n
            while l < r:
                m = (l + r) // 2
                if A[m] > T:
                    r = m 
                else:
                    l = m + 1
            return r - 1

        l = binarySearchLeft(nums, target)
        r_1 = binarySearchRight(nums, target)
        return [l, r_1] if l <= r_1 else [-1, -1]

i think this method is too confusing

class Solution:
    def searchRange(self, A: List[int], T: int) -> List[int]:
        def first_pos(a, x):
            n = len(a)
            L = 0
            R = n - 1

            ans = n # first >= x, smallest value greater than

            while L <= R:
                m = (L + R) // 2
                if a[m] < x:
                    L = m + 1
                else: # a[m] >= x
                    R = m - 1
            return L
        
        first = first_pos(A, T)
        last = first_pos(A, T + 1) - 1 # magic index
        if first <= last:
            return [first, last]
        return [-1, -1]