0035-search-insert-position.py

"""
35. Search Insert Position

Submitted: November 3, 2022

Runtime: 69 ms (beats 5.67%)
Memory: 14.68 MB (beats 100.00%)
"""

classSolution:
defsearchInsert(self, nums: List[int], target: int) ->int:
defbs(a, h, l, x): # begin binary search function
ifh>=l:
m= (h+l) //2
ifa[m] ==x:
returnm
elifa[m] >x:
returnbs(a, l, m-1, x)
else:
returnbs(a, l, m+1, x)
else:
return-1
# end binary search function
iftargetinnums:
r=bs(nums, len(nums), 0, target)
ifr>=0:
returnr
else: # O(n) fallback if binary search doesn't work
foriinrange(len(nums)):
j=nums[i]
ifj==target:
returni
else: # find the first position where nums[i] is greater than target,
iftarget>nums[-1]: # so we can insert *before* that position
returnlen(nums)
eliftarget<nums[0]:
return0
else:
foriinrange(len(nums)):
ifnums[i] >target:
returni
return-1# not found