Search Insert Position
Find where a target is, or where it would be inserted, in a sorted array with the lower-bound binary search template.
Problem Understanding
Search Insert Position: given a sorted array of distinct integers and a target, return the index of target if it is present, or the index where it would be inserted to keep the array sorted. It must run in O(log n).
Examples: in [1, 3, 5, 6], target 5 returns 2, target 2 returns 1, and target 7 returns 4.
The Intuition: One Question Covers Both Cases
"Where is it" and "where would it go" have the same answer: the first index whose value is ≥ target. If the target is present, that is its index; if not, it is the slot where it belongs.
Find that index with binary search over the half-open range [lo, hi):
- Start with
lo = 0,hi = n, so "after everything" (index n) is a valid answer. - Take
mid. Ifnums[mid] < target, the answer is to the right:lo = mid + 1. - Otherwise
midmight be the answer, so keep it:hi = mid. - When
lo == hi, returnlo.
This lower-bound loop is worth memorising: it never needs a special case for "found" and never goes out of bounds.
Interactive Walkthrough
Cells inside [lo, hi) are shaded, including the dashed slot for index n. Each step compares mid with the target and throws away half the range until lo and hi meet on the answer.
Dry Run Table
Input: [1, 3, 5, 6], target = 2
| lo | hi | mid | nums[mid] | Action |
|---|---|---|---|---|
| 0 | 4 | 2 | 5 | 5 ≥ 2: hi = 2 |
| 0 | 2 | 1 | 3 | 3 ≥ 2: hi = 1 |
| 0 | 1 | 0 | 1 | 1 < 2: lo = 1 |
| 1 | 1 | — | — | return 1 |
The Solution Template
The lower-bound binary search over [0, n).
Search Insert Position Code
1var searchInsert = function(nums, target) {2 let lo = 0, hi = nums.length;3 while (lo < hi) {4 const mid = (lo + hi) >> 1;5 if (nums[mid] < target) lo = mid + 1;6 else hi = mid;7 }8 return lo;9};
Edge Cases & Common Mistakes
- Target larger than everything: the answer is
n; starting withhi = n − 1would miss it. - Target smaller than everything: the answer is
0. hi = mid − 1: that can skip the very index you are looking for.- Overflow in other languages: compute
midaslo + (hi − lo) / 2where integers are fixed-width.
Summary
Both questions, where the target is and where it would go, ask for the first index with a value ≥ target. Binary search the half-open range [0, n): move lo past values that are too small, pull hi down onto values that are big enough, and return lo. O(log n) time, O(1) space.
More practice: DSA interview questions with answers · patterns cheat sheet