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