The problem
In a sorted list, return the position of the target, or the position where it should be inserted to keep the list sorted.
Input: [1, 3, 5, 6, 9, 12, 15], target = 7 Output: 4
Picture it
Picture slotting a new book into a sorted shelf. Binary search narrows down the gap: the first book bigger than (or equal to) the new one marks the spot.
Short version: the full lesson (brute force, complexity, edge cases and a quiz) is still being written. The animation is complete.
The key idea
Lower-bound binary search. O(log n).
Python solution
def search_insert(a, t):
lo, hi = 0, len(a)
while lo < hi:
mid = (lo + hi) // 2
if a[mid] < t:
lo = mid + 1
else:
hi = mid
return loIn the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.