Binary search: search insert position

Binary search finds a value in a sorted list by repeatedly halving the search space. Each step throws away half the remaining candidates, so it runs in O(log n) instead of O(n):

lo, hi = 0, len(nums) - 1
while lo <= hi:
    mid = (lo + hi) // 2
    # compare nums[mid] to the target, then move lo or hi

This is LeetCode #35. If the target is present, return its index. If not, return the index where it would go to keep the list sorted — which is exactly where lo lands when the loop ends.

Your task

Write search_insert(nums, target). nums is sorted ascending with distinct values. Return the index of target, or the insertion index that keeps nums sorted.

search_insert([1, 3, 5, 6], 5)   # 2   (found at index 2)
search_insert([1, 3, 5, 6], 2)   # 1   (would slot between 1 and 3)
search_insert([1, 3, 5, 6], 7)   # 4   (would go at the end)

Hint: keep lo/hi bounds. If nums[mid] == target return mid; if it is smaller, search the right half; otherwise the left. Return lo at the end.