Given a sorted array of distinct numbers and a target, return its index if found. Otherwise, return the index where it would be inserted to keep the order.
DSA Animator › DSA Revision › Binary Search › Search Insert Position
Remember: when binary search misses, low lands on the insert position. That makes low the first index with a value at least the target. The video solves Search Insert Position (LeetCode 35, Easy) with the Binary Search pattern from the Binary Search topic, and you can replay every step in the interactive Search Insert Position animation.
Given a sorted array of distinct numbers and a target, return its index if found. Otherwise, return the index where it would be inserted to keep the order.
For 1, 3, 5, 6 and target 2, the answer is 1. 2 belongs between 1 and 3.
Scanning for the first number that is at least the target is O of n. Binary search finds it in O of log n.
Run a normal binary search. If the target is never found, low ends at the first index whose value is bigger than the target. That is exactly the insert position.
Low 0, high 3, so mid is 1, holding 3, which is bigger than 2, so high becomes 0. Mid is 0, holding 1, which is smaller, so low becomes 1. Low passed high, so the search ends. Low is 1, the insert position.
In code, run the standard binary search loop. Return mid if it matches. Otherwise return low after the loop, so it's O of log n time.
Remember: when binary search misses, low lands on the insert position. That makes low the first index with a value at least the target.