35. Search Insert Position
You are given an array of distinct integers nums, sorted in ascending order, and an integer target.
If target is present in nums, return its 0-based index. If it is not, return the index at which it would have to be inserted to keep the array sorted — everything smaller stays on the left, everything larger shifts right. Inserting past the last element (index n) and before the first (index 0) are both possible answers.
The array is sorted, so solve it in O(log n) time.
Example 1:
Input: nums = [1, 3, 5, 6], target = 5
Output: 2
Explanation: 5 is already in the array, at index 2.
Example 2:
Input: nums = [1, 3, 5, 6], target = 2
Output: 1
Explanation: 2 is missing; slotting it between 1 and 3 puts it at index 1.
Example 3:
Input: nums = [1, 3, 5, 6], target = 7
Output: 4
Explanation: 7 is bigger than everything, so it goes after the end, at index 4.
Constraints:
- 1 ≤ nums.length ≤ 10⁴
- -10⁴ ≤ nums[i] ≤ 10⁴
- nums contains distinct values sorted in ascending order
- -10⁴ ≤ target ≤ 10⁴
Hints:
Found or not, the answer is the same number: the position of the first element that is >= target (or n when every element is smaller).
That is a lower-bound binary search on the half-open window [lo, hi): move lo past values < target, pull hi down onto values >= target, and answer lo when they meet.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: nums = [1, 3, 5, 6], target = 5
Expected output: 2