Where a value belongs in a sorted array
Given a sorted array nums of distinct integers and an integer target, return
the index of target if it is present. Otherwise return the index where it would have to be inserted
to keep the array sorted. Use O(log n) comparisons.
Examples
| Input | Output | Why |
|---|---|---|
nums = [1, 3, 5, 6], target = 5 | 2 | |
nums = [1, 3, 5, 6], target = 2 | 1 | 2 goes between 1 and 3. |
nums = [1, 3, 5, 6], target = 7 | 4 | After the last element: the length of the array. |
Constraints
- 1 ≤ n ≤ 10⁴
- −10⁴ ≤ nums[i], target ≤ 10⁴
- nums is strictly increasing
Hints
Hint 1
Both cases ask for the same index: the first position whose element is at least target.
Hint 2
The test "nums[i] ≥ target" is false for a prefix of the array and true for the rest. Search for the first true.
Hint 3
Let hi start at n, one past the end, so that "every element is smaller" has an answer to land on.
Where people lose marks
- Starting with hi = n − 1, which leaves no way to return n when target is larger than everything.
- Mixing the closed-range exact search with the half-open lower bound:
hi = mid − 1in a lower bound skips the answer. - Returning mid instead of lo after the loop.
Dry run on [2,5,9,14,20,27,33,41],15
Read it one frame at a time, the way you would trace the code on paper in an interview. Each frame shows the state after the step it describes.
-
Step 1 / 5lo0hi8
We want the first index with a value ≥ 15. The answer is in [lo, hi) = [0, 8); hi = 8 stands for "nothing passes".
-
Step 2 / 5lo0mid4hi8
a[4] = 20: 20 ≥ 15. It passes, so the first pass is at 4 or earlier: hi = 4.
-
Step 3 / 5lo0mid2hi4
a[2] = 9: 9 < 15. It fails, and so does everything before it: lo = 3.
-
Step 4 / 5lo3mid3hi4
a[3] = 14: 14 < 15. It fails, and so does everything before it: lo = 4.
-
Step 5 / 5answer4
lo = hi = 4. Index 4 is the first index with a value ≥ 15. 15 is not present; it would be inserted at index 4.
How to think about it
If target is present, its index is the first position holding a value
≥ target. If it is absent, the insertion point is again the first position holding a value
≥ target, or n if there is none. So the problem is one search: the lower bound.
The test nums[i] ≥ target reads false, false, …, true, true along a sorted array. Keep a
half-open range [lo, hi) that always contains the first true, with hi = n standing for
"no element passes":
- If
nums[mid] ≥ target, the first true is atmidor before:hi = mid. - Otherwise it is after
mid:lo = mid + 1.
When lo = hi the range holds one candidate, and that is the answer. No equality test is needed, and
the loop never exits early.
Every standard library has this search: bisect_left in Python,
std::lower_bound in C++, partition_point in Rust. Interviewers usually want it written
out, and then accept the library call in later problems.
Complexity. Time O(log n) · Space O(1)
The solution, in six languages
Each one is compiled and run against the test table before it is published. Java is reviewed by hand.
def search_insert(nums, target):
lo, hi = 0, len(nums) # the answer is in [lo, hi); hi = n means "after everything"
while lo < hi:
mid = (lo + hi) // 2
if nums[mid] >= target:
hi = mid # mid passes: the first pass is mid or earlier
else:
lo = mid + 1 # mid fails, and so does everything before it
return lo#include <vector>
int solve(const std::vector<int>& nums, int target) {
int lo = 0, hi = (int)nums.size(); // the answer is in [lo, hi)
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (nums[mid] >= target) hi = mid; // mid passes
else lo = mid + 1; // mid fails
}
return lo; // same as std::lower_bound(...) - nums.begin()
}class Solution {
public int searchInsert(int[] nums, int target) {
int lo = 0, hi = nums.length; // the answer is in [lo, hi)
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (nums[mid] >= target) hi = mid; // mid passes
else lo = mid + 1; // mid fails
}
return lo;
}
}function searchInsert(nums, target) {
let lo = 0, hi = nums.length; // the answer is in [lo, hi)
while (lo < hi) {
const mid = lo + ((hi - lo) >> 1);
if (nums[mid] >= target) hi = mid; // mid passes
else lo = mid + 1; // mid fails
}
return lo;
}fn solve(nums: &[i64], target: i64) -> i64 {
let (mut lo, mut hi) = (0usize, nums.len()); // the answer is in [lo, hi)
while lo < hi {
let mid = lo + (hi - lo) / 2;
if nums[mid] >= target { hi = mid } else { lo = mid + 1 }
}
lo as i64 // the library call: nums.partition_point(|&x| x < target)
}import Data.Array
solve :: [Int] -> Int -> Int
solve nums target = go 0 n
where
n = length nums
a = listArray (0, n - 1) nums
-- the answer is in [lo, hi)
go lo hi
| lo >= hi = lo
| a ! mid >= target = go lo mid
| otherwise = go (mid + 1) hi
where mid = lo + (hi - lo) `div` 2Variants to try
- With duplicates, the same code returns the first occurrence. The last occurrence is the first index with nums[i] > target, minus one.
- Count the elements equal to target: upper bound minus lower bound.
- Count elements in a range [a, b]: lower bound of b + 1 minus lower bound of a.
Next problems
First and last position of a value
Two lower-bound searches, one for "at least target" and one for "greater than target", give both ends of the run.
Open the problem → Medium20 minCount the partners that clear a threshold
Sort one list once; each query then becomes one lower-bound search for the smallest partner that is good enough.
Open the problem → Medium15 minResearch impact from sorted citation counts
The test compares each count with how many papers lie to its right; that test is monotone, so a lower bound finds the h-index.
Open the problem →Write a solution and run it against the real test table.
Keep going
First and last position of a value
Two lower-bound searches, one for "at least target" and one for "greater than target", give both ends of the run.
Open the problem → Medium20 minCount the partners that clear a threshold
Sort one list once; each query then becomes one lower-bound search for the smallest partner that is good enough.
Open the problem → Medium15 minResearch impact from sorted citation counts
The test compares each count with how many papers lie to its right; that test is monotone, so a lower bound finds the h-index.
Open the problem → Binary searchThe pattern behind it
Search the answer, not the array: halve a monotone predicate until one candidate is left.
Read the pattern →Preparing for a real process? Quant interview preparation, or book a free 20-minute call.