Algorithm

Search Insert Position

Binary Search Pattern

Search Insert Position

Given a sorted array of distinct integers and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order. You must write an algorithm with O(log n) runtime complexity.

CONSTRAINTS
  • 1 <= nums.length <= 10^4
  • -10^4 <= nums[i], target <= 10^4
  • nums contains distinct values sorted in ascending order
EXAMPLE 1
Input: nums = [1,3,5,6], target = 5
Output: 2
Target 5 is found at index 2.
EXAMPLE 2
Input: nums = [1,3,5,6], target = 2
Output: 1
Target 2 is not found. It would belong at index 1 (between 1 and 3).
What should be returned if the target is larger than all existing elements?
In that case, return the length of the array, as the target would be appended to the end.
Can the array contain duplicate values?
The current constraints specify distinct integers, so you don't need to worry about duplicates.

This problem is a tiny twist on standard Binary Search. Instead of just searching for an index, we are searching for a "Gap."

The Brute Force Idea

You could walk through the array (O(N)) and find the first number that is greater than or equal to your target. That index is your answer. While simple, it's too slow for large sorted arrays.

The Boundary Discovery

Binary Search is more than a "finder"—it is a "folder." Every time you check the middle, you fold the search window in half.
If the target is missing, the two pointers (left and right) will keep squeezing together until they eventually "cross" each other.

The "Left" Revelation

At the exact moment the pointers cross (when left > right), the search has failed to find the target. But something amazing happens: the "left" pointer is now pointing exactly at the first number in the array that is strictly larger than the target.
In other words, 'left' has landed precisely on the correct insertion index.

Code Blueprint
text
left = 0
right = length - 1

WHILE left <= right:
    mid = left + (right - left) / 2
    
    IF nums[mid] == target:
        RETURN mid
    ELSE IF nums[mid] < target:
        left = mid + 1
    ELSE:
        right = mid - 1

// If we reach here, the target was missing.
// The 'left' pointer marks the first element > target.
RETURN left
Why the Pattern is King

Searching for an insertion point is essentially finding the "Lower Bound" of a value. Since the array is sorted, we can find this boundary in O(log N) rather than checking every element. The pattern is optimal here because the property of "where a number belongs" is monotone—numbers to the left are smaller, numbers to the right are larger.

Interactive Strategy Visualization

Search Insert Intuition

Where does 14 belong?

1
Left
3
5
8
12
15
18
20
Right

Seeding the Search Space

We start with the full sorted array. We want to find either '14' or where it belongs.

Key Observation

As the search bounds collapse, the Left pointer is pushed forward whenever we find elements smaller than our target.

O(N) linear scan
→
O(log N) binary search