Binary Search · LC #35
Search Insert Position
Given a sorted array of distinct integers and a target, return the index where target is found, or the index where it would be inserted to maintain sorted order - in O(log n).
Statement
Problem & Approach
Problem statement, sample I/O, and key reasoning.
Given a sorted array of distinct integers `nums` and an integer `target`, return the index if the target is found. If not, return the index where it would be inserted in order. You must write an algorithm with O(log n) runtime complexity.
Sample I/O
Input: nums = [1,3,5,6], target = 5 Output: 2 Input: nums = [1,3,5,6], target = 2 Output: 1 Input: nums = [1,3,5,6], target = 7 Output: 4
Time: O(log n) · Space: O(1)
Intuition
How to Think About It
Intuition
Standard binary search terminates with `l == r+1`, at which point `l` is exactly the leftmost position where target could be inserted to keep the array sorted - the same as C++ `lower_bound` / Python `bisect_left`.
Core Concept
Run identical binary search logic. On a hit return `mid`. On a miss the loop exits with `l > r`; at that point every element left of `l` is strictly less than target, and every element at `l` or beyond is greater - so `l` is the correct insertion index.
When to use
Whenever you need either the exact position of a value or its insertion point in a sorted collection; also used as a subroutine in lower-bound queries.
When NOT to use
When the array is unsorted, or when you need the upper bound (last valid insertion position) - use `bisect_right` / `upper_bound` instead.
Key Insights
What to Know Cold
- The key insight: at loop termination `l` is always the lower-bound insertion index, whether or not the target was found.
- Returning `l` (not `r`) on miss is crucial - `r` ends at `l-1` after the final narrowing step.
- Python's `bisect.bisect_left(nums, target)` is a one-liner equivalent with the same O(log n) complexity.
- This problem is the canonical gateway to "binary search for answer" problems - the miss-return-`l` pattern recurs in many medium/hard variants.
- Works unchanged on empty arrays: loop never executes, returns `l=0` which is the only valid insert position.
3 examples
Worked Examples
Target present
nums=[1,3,5,6], target=5.
l=0,r=3. mid=1→3<5→l=2. mid=2→5==5→return 2.
function searchInsert(nums: number[], target: number): number {
let l=0, r=nums.length-1;
while(l<=r){
const m=l+Math.floor((r-l)/2);
if(nums[m]===target) return m;
else if(nums[m]<target) l=m+1;
else r=m-1;
}
return l;
}Output: 2
Shows the algorithm works identically whether target exists or not.
Target absent - insert in middle
nums=[1,3,5,6], target=2.
Loop exits with l=1, r=0. Return l=1 (between indices 0 and 1).
Output: 1
Demonstrates the miss path - `l` is left pointing at the correct gap.
Target beyond all elements
nums=[1,3,5,6], target=7.
Every mid value < 7, so l advances past r. l ends at 4 (== length).
Output: 4
Edge case: insertion at the tail; l equals array length, which is valid.