35. Search Insert Position

class Solution:
    def bs(self,arr,l,r,x):
        if l<=r:
            m = l + (r-l) // 2
            if arr[m] == x:
                return m
            elif arr[m] > x:
                return self.bs(arr,l,m-1,x)
            else:
                return self.bs(arr,m+1,r,x)
        else:
            return l
        
    def searchInsert(self, nums: List[int], target: int) -> int:
        return self.bs(nums,0,len(nums)-1,target)