Search Insert Position
Understand the problem
You're given an ascending sorted integer array nums (no duplicates) and an integer target. Return the index of target if it is found. If not, return the index where target would be inserted to keep the array sorted.
Example:
nums = [1, 3, 5, 6], target = 5
output = 2 // nums[2] = 5, found
nums = [1, 3, 5, 6], target = 2
output = 1 // 2 would be inserted at index 1, between 1 and 3
nums = [1, 3, 5, 6], target = 7
output = 4 // 7 would be inserted at the end of the arrayThis is a classic binary search variant — when the loop ends, low is exactly the insertion position.
Show the basic approach (slower)
O(n) time, O(1) spacefunction searchInsert(nums: number[], target: number): number {
for (let i = 0; i < nums.length; i++) {
if (nums[i] >= target) return i
}
return nums.length // target is larger than every element
}A linear scan ignores the fact that the array is sorted.
Binary search does the same job in O(log n).
Optimal solution
O(log n) time, O(1) spacefunction searchInsert(nums: number[], target: number): number {
let low = 0
let high = nums.length - 1
while (low <= high) {
const mid = Math.floor((low + high) / 2)
if (nums[mid] === target) return mid
if (nums[mid] < target) low = mid + 1
else high = mid - 1
}
// After the loop, low is the correct insert position
return low
}The optimal approach has the same structure as classic binary search; only the return value differs when the target is not found.
When the loop ends (low > high), low always points to the first position whose value is greater than target — exactly where it should be inserted.
Step-by-step trace
1function searchInsert(nums: number[], target: number): number {2 let low = 03 let high = nums.length - 14 while (low <= high) {5 const mid = Math.floor((low + high) / 2)6 if (nums[mid] === target) return mid7 if (nums[mid] < target) low = mid + 18 else high = mid - 19 }10 // After the loop, low is the correct insert position11 return low12}Edge cases to remember
Target smaller than every element (nums=[3,5], target=1) — high drops to -1, low=0 → insert at the front.
Target larger than every element (nums=[1,3], target=5) — low reaches nums.length → insert at the end.
One-element array — a single comparison is enough to determine the position.
Target exactly equal to the first or last element — still returns the right index thanks to the === check in the loop.