Search Insert Position
Find the index of a target in a sorted array, or the index where it should be inserted, using the lower-bound form of binary search in O(log n).
Updated Short read: 4 min read
Approaches at a glance
| Approach | Time | Space |
|---|---|---|
| Linear scan | O(n) | O(1) |
| Binary search (lower bound) | O(log n) | O(1) |
The problem
You are given an array of distinct integers sorted in ascending order, and a target. If the target is in the array, return its index. If it is not, return the index where it would have to be inserted to keep the array sorted. The solution must run in O(log n) time.
numbers = [1, 3, 5, 6], target = 5 → 2 (found)
numbers = [1, 3, 5, 6], target = 2 → 1 (between 1 and 3)
numbers = [1, 3, 5, 6], target = 7 → 4 (after everything)
numbers = [1, 3, 5, 6], target = 0 → 0 (before everything)Restating the question
Both cases have the same answer: the index of the first element that is greater than or equal to the target.
- If the target is present, that element is the target itself.
- If it is absent, that element is the one the target must be placed in front of.
- If no element is large enough, the answer is the array's length.
This value is called the lower bound, and finding it is one search rather than two cases.
Approach 1: linear scan
JavaScript
function searchInsertLinear(numbers, target) {
for (let i = 0; i < numbers.length; i++) {
if (numbers[i] >= target) return i;
}
return numbers.length;
}Python
def search_insert_linear(numbers, target):
for i, value in enumerate(numbers):
if value >= target:
return i
return len(numbers)Time O(n). Space O(1).
Approach 2: binary search for the lower bound
JavaScript
function searchInsert(numbers, target) {
let lo = 0;
let hi = numbers.length;
while (lo < hi) {
const mid = lo + Math.floor((hi - lo) / 2);
if (numbers[mid] < target) {
lo = mid + 1;
} else {
hi = mid;
}
}
return lo;
}Python
def search_insert(numbers, target):
lo = 0
hi = len(numbers)
while lo < hi:
mid = lo + (hi - lo) // 2
if numbers[mid] < target:
lo = mid + 1
else:
hi = mid
return loThis differs from the exact-match binary search in three connected ways:
histarts atnumbers.length, one past the last index, because "after everything" is a possible answer.- The loop runs while
lo < hiand ends when the two meet. That meeting point is the answer. hi = mid, notmid - 1. Whennumbers[mid]is greater than or equal to the target,midmight be the answer, so it stays in the range.
When numbers[mid] is less than the target, mid and everything before it are too small, so lo moves to mid + 1.
Walkthrough
numbers = [1, 3, 5, 6], target = 2:
| lo | hi | mid | numbers[mid] | Action |
|---|---|---|---|---|
| 0 | 4 | 2 | 5 | 5 ≥ 2, so hi = 2 |
| 0 | 2 | 1 | 3 | 3 ≥ 2, so hi = 1 |
| 0 | 1 | 0 | 1 | 1 < 2, so lo = 1 |
| 1 | 1 | lo equals hi: return 1 |
Time O(log n). Space O(1).
Both templates are compared in the binary search pattern.
Try it yourself
Copy a solution from above, add the lines below, and run it. For JavaScript, paste both into the browser console, or save them in a file and run it with node. For Python, save them in a file and run it with python.
JavaScript
console.log(searchInsert([1, 3, 5, 6], 5)); // 2
console.log(searchInsert([1, 3, 5, 6], 2)); // 1
console.log(searchInsert([1, 3, 5, 6], 7)); // 4Python
print(search_insert([1, 3, 5, 6], 5)) # 2
print(search_insert([1, 3, 5, 6], 2)) # 1
print(search_insert([1, 3, 5, 6], 7)) # 4The comment after each line is the result you should see.
Common mistakes
- Starting
hiatnumbers.length - 1. A target larger than every element would then never get the answernumbers.length. - Using
hi = mid - 1in this version. That can discard the answer. - Handling "found" and "not found" separately. It works, but it is more code and more places for an off-by-one error.
Original problem: LeetCode 35: Search Insert Position