Pattern visualizer

Search Insert Position

The insight: binary search doesn't just locate an exact match — the way it narrows left and right also pins down exactly where the value would go if it were missing. Every time nums[mid] is too small, left moves past it, so everything before the new left is provably smaller than the target; every time nums[mid] is too big, right moves before it, so everything after the new right is provably bigger. When the loop ends, left sits exactly on the boundary between "too small" and "too big" — that boundary IS the insertion point, whether or not the target was actually present. This trace shows the case where target=5 IS found at index 2, short-circuiting the loop before it ever needs to fall back on that boundary. Animated on: Given a sorted array of distinct integers and a target value, return the index if the target is found. If not, return the index where it would be if inserted in order..