DSA AnimatorDSA animations
Search Insert Position LC #35 Easy Binary Search
Problem

Given a sorted array of distinct integers nums and a target value, 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.

Example 1
Input: nums = [1,3,5,6], target = 5
Output: 2
Explanation: 5 is found at index 2.
Example 2
Input: nums = [1,3,5,6], target = 2
Output: 1
Explanation: 2 would be inserted between index 0 (value 1) and index 1 (value 3).
Example 3
Input: nums = [1,3,5,6], target = 7
Output: 4
Explanation: 7 is larger than all elements — insert at the end.
Constraints: 1 ≤ nums.length ≤ 10⁴  |  −10⁴ ≤ nums[i], target ≤ 10⁴  |  All integers in nums are distinct and sorted ascending.
Try Examples
Custom:
Array
target —
Variables
lo
—
hi
—
mid
—
nums[mid]
—
comparison
—
Step Logic
Press ▶ Play or Next Step to begin the animation.
✓
Ready
0 / 0
Select an example above and press Play.
Algorithm
1
Init lo = 0, hi = nums.length − 1
2
While lo ≤ hi: compute mid = lo + (hi−lo)/2
3
If nums[mid] == target → return mid (found)
4
If nums[mid] < target → lo = mid + 1 (search right half)
5
Else → hi = mid − 1 (search left half)
6
Loop ends: lo is the insertion point — return lo
Time
O(log n)
Space
O(1)
Why lo is the Insert Position

Loop invariant: at every step the answer lies in [lo, hi+1]. When lo > hi the range collapses and lo points to the first index where nums[lo] > target — exactly where target must be inserted to preserve sorted order. This works whether target is smaller than all elements (lo stays 0), larger than all (lo becomes n), or anywhere in between.

How to solve Search Insert Position

LeetCode 35 · Easy · Binary Search · Pattern: Binary Search

Why the obvious approach is slow

Scanning for the first number that is at least the target is O(n). Binary search finds it in O(log n).

The key idea

Run a normal binary search. If the target is never found, low ends at the first index whose value is bigger than the target. That is exactly the insert position.

Remember

When binary search misses, low lands on the insert position. That makes low the first index with a value at least the target.

Run the animation above on your own input, or watch the 1:08 video explanation of Search Insert Position with a dry run and Java code.

More Binary Search problems