Search Insert Position
Module 13 · Binary Search
Problem
Given a sorted array of distinct integers and a target, return the index if the target is found. If not, return the index where it would be inserted to keep the array sorted.
Examples
Example 1
Input
nums = [1,3,5,6], target = 5Output2Explanation. found at index 2
Example 2
Input
nums = [1,3,5,6], target = 2Output1Explanation. would insert between 1 and 3
Example 3
Input
nums = [1,3,5,6], target = 7Output4Explanation. would insert at the end
Example 4
Input
nums = [1,3,5,6], target = 0Output0Explanation. would insert at the start
Constraints
1 ≤ n ≤ 10⁴ · sorted, distinct values.
Attempt it first
This problem is the boundary-search lesson's lower_bound, verbatim —
"where would target go" and "first index with arr[i] >= target" are
the same question when values are distinct. The exercise is recognizing
that identity, not writing new code.