Easy Bisect Left Binary Search
In plain English: Find the leftmost position where you could insert a number into a sorted list and keep it sorted.
Bisect-left finds the first position where target could go — when the loop ends, lo points to the insertion point because all elements left of lo are strictly less.
Prompt
Given a sorted array and a target, return the index where the target would be inserted to keep the array sorted (bisect_left).
Try to write it from scratch before scrolling down.
Solution
def search_insert(a, target):
lo, hi = 0, len(a)
while lo < hi:
mid = (lo + hi) // 2
if a[mid] < target:
lo = mid + 1
else:
hi = mid # a[mid] >= target, could be the answer
return lo
# Test: search_insert([1,3,5,6], 5) == 2
# Test: search_insert([1,3,5,6], 2) == 1
# Test: search_insert([1,3,5,6], 7) == 4