← DSA Atlas
Dedicated problem page · #35

Search Insert Position

EasyBinary SearchLower-bound binary searchHalf-open binary search for insertion index
Solve on LeetCode ↗
35
EasyBinary SearchHalf-open binary search for insertion indexLower-bound binary search

Search Insert Position

Given a sorted array of distinct integers and a target, return the index if the target is found. If not, return the index where it would be inserted to keep the array sorted. You must run in O(log n) time.

Open official problem prompt ↗
In plain English

Locate a target in a sorted array, or the exact slot it would occupy, using logarithmic search.

Picture it like this

Like slipping a new book onto an alphabetized shelf: you binary-search to the first title that is not before yours, and that gap is where the book goes.

Example
Input
nums = [1, 3, 5, 6], target = 5
Output
2
Why
The value 5 is already present at index 2.
Constraints
1 <= nums.length <= 10^4-10^4 <= nums[i] <= 10^4nums contains distinct values sorted in ascending order-10^4 <= target <= 10^4
Pattern lesson

See the pattern, then code

Lower-bound binary search
Recognition clue

A sorted array plus 'find it or where it would go' in log time is the definition of a lower-bound binary search.

↗
Binary Search

Sorted data or a monotonic true/false condition over a possible answer.. The insertion index is simply the first position whose value is >= target; if that value equals target it is a hit, otherwise it is exactly where target belongs.

New words, made simpleKnow these before the algorithm
Insertion index
The position where inserting target keeps the array sorted, equal to the count of elements strictly less than target.
Half-open window
Using hi = len(nums) so the returned index may validly be one past the last element.
Approaches from first idea to best ideaCompare the trade-offs
ApproachHow it thinksCost
Linear scan

Simple but violates the O(log n) requirement.

Advance until you find target or a larger value.

Time O(n)Space O(1)
Best choiceLower-bound binary search

Optimal and doubles as both search and insertion.

Binary-search the first index with value >= target.

Time O(log n)Space O(1)
The rule we keep true

Invariant

Every index below lo holds a value strictly less than target, and every index at or above hi holds a value >= target.

Why this is correct

Reasoning

The invariant means lo can only ever land on the first index whose value is not less than target. If that value equals target it is the found index; if it is greater, target belongs just before it, which is the same index. Elements strictly less than target are all left of lo, so lo is exactly the correct insertion point.

The algorithm in three movesSay these aloud before coding
1Set lo = 0 and hi = len(nums) as a half-open window

lo=0, hi=4, mid=2 -> nums[2]=5, not < 5, hi=2

2While lo < hi, compute mid

lo=0, hi=2, mid=1 -> nums[1]=3 < 5, lo=2

3If nums[mid] < target, the answer is right of mid, so lo = mid + 1

lo==hi==2 -> return 2

4Otherwise the answer is mid or left, so hi = mid

5Return lo, which is both the found index and the insertion point

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example
10
31
52
63
1 · Readlo=0, hi=4, mid=2
2 · AskIs nums[2]=5 < 5?
3 · Update statenot less
4 · Resulthi = 2
Key takeaway

The search collapses onto index 2, where 5 already sits.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

  1. 1
    Lines 3Half-open bounds

    hi = len(nums) allows the answer to be the array length when target exceeds every element.

  2. 2
    Lines 6-7Discard the left

    nums[mid] < target means target belongs strictly right, so lo skips past mid.

  3. 3
    Lines 8-9Keep the candidate

    Otherwise mid could be the answer, so hi = mid retains it.

Make it stick

Edge cases, mistakes, and one self-check

E

Edge cases to test

  • Target smaller than every element (returns 0)
  • Target larger than every element (returns len(nums))
  • Single-element array
  • Target already present
!

Common beginner mistakes

  • Using hi = len(nums) - 1, which cannot return the past-the-end insertion index
  • Combining lo <= hi with hi = mid, causing an infinite loop
  • Returning mid instead of lo, which may miss the boundary when the loop exits
Check your understanding

Why can this same lower-bound routine both find a value and give its insertion point?

More in Binary Search

#33Search in Rotated Sorted ArrayBinary search on a rotated array#153Find Minimum in Rotated Sorted ArrayBinary search for the rotation point#875Koko Eating BananasBinary search on the answer#4Median of Two Sorted ArraysBinary search on the partition#34Find First and Last Position of ElementLower-bound binary search on both ends#74Search a 2D MatrixBinary search on a flattened grid