Why don’t they just call it binary search? The runtime requirement is a giveaway — and for people who are “fluent” enough with runtime complexity to understand O(lg n) but don’t yet know about binary search, you are a rare breed, I’d think.
So I’ll spare you the usual C++ std::algorithm implementation. I like this loop. I think a lesson where we really 100% understand the intuition behind binary search, and then having students actually implement it, could be a nice hour.
class Solution(object):
def searchInsert(self, nums, target):
lb = 0
ub = len(nums)
while lb < ub:
mid = (lb+ub)/2
#print(lb, mid, ub)
searchValue = nums[mid]
# Feels hacky... can we do something smarter?
if mid == lb:
assert(ub == lb + 1)
if searchValue < target:
return ub
return lb
if searchValue > target:
ub = mid
elif searchValue < target:
lb = mid
else:
return mid
#print("done", lb, ub)
assert(lb == ub)
return lb