Given a sorted array of distinct integers nums and a target, return the index of target if it is present. If it is not, return the index where it would be inserted to keep the array sorted.
Your algorithm must run in O(log n) time.
Example
5 is at index 2.
Constraints
- 1 <= nums.length <= 10^4
- -10^4 <= nums[i] <= 10^4
- nums contains distinct values sorted in ascending order.
- -10^4 <= target <= 10^4
Intuition
The plain approach scans left to right and stops at the first element that is >= target — that index either holds the target or is the slot it belongs in. If nothing is large enough, it belongs at the end.
function searchInsert(nums, target) {
// Walk left to right; the first slot not smaller than target is the answer.
for (let i = 0; i < nums.length; i++) {
if (nums[i] >= target) return i; // found it, or the gap it slots into
}
return nums.length; // larger than everything — goes at the end
}This is O(n) — but the array is sorted, and the prompt demands O(log n), so the scan wastes the ordering. Can we do better?
The values < target form a prefix and the values >= target form a suffix; we want the boundary between them. That's a textbook lower-bound binary search: keep a half-open range [lo, hi), and at each step look at mid. If nums[mid] < target, the boundary is strictly to the right, so lo = mid + 1; otherwise mid is a candidate boundary, so hi = mid to keep it. When lo === hi, lo is the first index whose value is >= target — the insertion point.
Walking it through:
nums = [1, 3, 5, 6], target = 2
Range is [0, 4). nums[2] = 5 is not below 2, so the boundary is at index 2 or to its left — keep mid.
Now [0, 2). nums[1] = 3 is still not below 2 — discard the right half again.
nums[0] = 1 is below 2, so index 0 is too small — push lo past it.
The range is empty. 2 belongs at index 1, between 1 and 3.
Optimization
Lower-bound binary search
Find the leftmost index whose value is >= target by binary search. If target is present that index holds it; if not, it is exactly the slot where target would be inserted to stay sorted. Both cases collapse to the same answer.
O(log n) time, O(1) space.
function searchInsert(nums, target) {
let lo = 0;
let hi = nums.length;
while (lo < hi) {
const mid = (lo + hi) >> 1;
if (nums[mid] < target) lo = mid + 1;
else hi = mid;
}
return lo;
}Complexity analysis
Time complexity: O(log n). Here's why:
- Each iteration discards half the remaining range by moving
loorhitomid. - Starting from
ncandidate positions, the range halves until it is empty.
So the loop runs about log₂ n times — overall O(log n).
Space complexity: O(1). Here's why:
- Only the two integer bounds
loandhiare kept; nothing scales with the input.
The returned index is a single number, not counted as extra space — overall O(1).
Test cases
Beyond the example above, these are worth thinking through before you submit.
| Input | Expected output | Description |
|---|---|---|
| nums = [], target = 5 | 0 | Empty array — the target slots at index 0. |
| nums = [3], target = 3 | 0 | Single element equal to the target — found at index 0. |
| nums = [10,20,30], target = 5 | 0 | Smaller than everything — inserts at the front. |
| nums = [2,2,2], target = 2 | 0 | All equal to the target — the lower bound is index 0. |
| nums = [1,1,3,3,5], target = 3 | 2 | Duplicates — returns the first index whose value is >= target. |
| nums = [1,2], target = 9 | 2 | Larger than everything — inserts at the end (index length). |
Try it yourself
Write your solution against the real judge before checking the reference.