Search Insert Position
Use binary search to find an existing index or insertion boundary.
Try It Yourself
Use the editor below to find the first index whose value is greater than or equal to the target. That index is both the target position and the correct insertion position.
Submit your implementation when it passes the examples. Test targets before the first value, after the last value, and between two values.
Search Insert Position
Given a sorted array of distinct integers and a target, return the target's index when present.
Otherwise, return the index where the target should be inserted to keep the array sorted.
Example 1:
Example 2:
Constraints
1 ≤ nums.length ≤ 10,000- nums is strictly increasing.
Solution
Treat the right boundary as one position past the array. When the middle value is smaller than the target, discard it and everything to its left. Otherwise, keep the middle position as a possible answer and move the right boundary to it.
When the boundaries meet, that position is the lower bound for the target.
function searchInsert(nums, target) {
let left = 0;
let right = nums.length;
while (left < right) {
const middle = left + Math.floor((right - left) / 2);
if (nums[middle] < target) left = middle + 1;
else right = middle;
}
return left;
}Big O notation
| Measure | Complexity | Explanation |
|---|---|---|
| Time | O(log n) | Every comparison removes about half of the remaining positions. |
| Auxiliary space | O(1) | Only the search boundaries and middle index are stored. |