LC 0035 [E] Search Insert Position - ALawliet/algorithms GitHub Wiki

return the index if target is found, else return where it will be inserted
=> find the smallest/first index that is greater than target
=> leftmost

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