Search Insert Position: Binary Search for the Insertion Point

Search Insert Position is LeetCode 35, and it is one of the best problems for solidifying binary search fundamentals. If you already know the standard binary search template from LeetCode 704, this problem asks one small but important question: what happens when the target is not in the array?

The answer reveals something elegant about binary search. The lo pointer does not just fail to find the target. It converges to exactly the index where the target belongs.

The problem

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 inserted in order. You must write an algorithm with O(log n) runtime complexity.

Examples:

• nums = [1, 3, 5, 6], target = 5 returns 2 (found at index 2)
• nums = [1, 3, 5, 6], target = 2 returns 1 (would be inserted at index 1)
• nums = [1, 3, 5, 6], target = 7 returns 4 (would be inserted at the end)

The approach

You run a standard binary search with inclusive bounds. If you find the target, return mid. If the loop ends without finding the target, return lo.

Why does lo give the correct insertion index? Think about what the loop does. At each step, lo moves right past elements that are smaller than the target, and hi moves left past elements that are larger. When the loop ends with lo > hi, every element before index lo is smaller than the target, and every element at index lo or later is larger. That is exactly where the target should go.

This is the same binary search template you already know. The only difference is the return value on the "not found" path: lo instead of -1.

Visual walkthrough

Let's search for 2 in [1, 3, 5, 6]. Watch how lo converges to the insertion point.

After two comparisons, lo sits at index 1. That is exactly where 2 belongs: after 1 and before 3.

The code

def searchInsert(nums, target):
    lo, hi = 0, len(nums) - 1

    while lo <= hi:
        mid = lo + (hi - lo) // 2

        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1

    return lo

Let's walk through each piece:

• lo, hi = 0, len(nums) - 1 initializes the search space as the full array with inclusive bounds.
• while lo <= hi keeps going as long as there is at least one element to check.
• mid = lo + (hi - lo) // 2 computes the midpoint safely, avoiding overflow in languages like Java and C++.
• if nums[mid] == target: return mid handles the case where the target exists in the array.
• lo = mid + 1 moves lo past elements confirmed to be smaller than the target.
• hi = mid - 1 moves hi past elements confirmed to be larger than the target.
• return lo is the key line. When the target is not found, lo points to the first index where the value is greater than the target, which is the correct insertion position.

Why lo is the insertion index

This is worth understanding deeply because the same reasoning applies to many binary search variants.

Consider the moment the loop exits. At that point, lo == hi + 1. Every element at index 0 through hi is strictly less than the target (because lo moved past each of them). Every element at index lo through the end is strictly greater than the target (because hi moved past each of them). So index lo is the boundary between "too small" and "too large," which is exactly where the target should be inserted.

This also works at the edges. If the target is smaller than every element, lo never moves and stays at 0. If the target is larger than every element, lo moves past the last index and ends at len(nums).

Complexity analysis

Time: O(log n). Each iteration halves the search space, giving at most log2(n) iterations.

Space: O(1). Only three variables (lo, hi, mid) are used regardless of input size.

Edge cases

Target smaller than all elements. nums = [3, 5, 7], target = 1. The loop compares 1 against every midpoint, always going left. lo never advances and stays at 0. Correct: 1 would be inserted at index 0.

Target larger than all elements. nums = [1, 3, 5], target = 8. The loop always goes right. lo advances past the last element to index 3 (which equals len(nums)). Correct: 8 would be inserted at the end.

Target exists in the array. nums = [1, 3, 5, 6], target = 5. Standard binary search finds it at index 2 and returns early. The insertion logic is never reached.

Single element. nums = [3], target = 3 returns 0 (found). target = 1 returns 0 (insert before). target = 5 returns 1 (insert after). All handled correctly by the template.

The building blocks

This problem is built from two core building blocks:

Binary search convergence. The standard mechanism of maintaining [lo, hi], computing a midpoint, and eliminating half the range. This is the same engine that powers LeetCode 704, Search in Rotated Sorted Array, Find Minimum in Rotated Sorted Array, and dozens of other problems.

Insertion point from lo. The insight that when binary search finishes without a match, lo sits at the exact position where the target belongs. This same idea is the foundation of Python's bisect_left, C++'s lower_bound, and Java's Arrays.binarySearch (which returns -(insertion point) - 1 when the target is missing). You will see this pattern again in problems like First Bad Version and finding the leftmost occurrence in an array with duplicates.

From understanding to recall

You understand why lo gives the insertion index. You can trace through the examples. But can you write the solution from scratch in 60 seconds with no reference? That is the gap between understanding and recall.

Under interview pressure, small doubts stack up. You might wonder whether to return lo or hi or mid. You might second-guess the loop condition. These are not hard questions, but if you have not practiced writing the code from memory, they cost you time and confidence when it matters.

Spaced repetition closes that gap. You type the solution today, again tomorrow, then in three days, then a week. Each repetition from memory, not from a reference. After a few rounds, you write return lo on the not-found path without any hesitation, and you spend your interview time on the problems that actually require creative thinking.

Related posts

• Binary Search: More Than Finding a Number - The complete guide to binary search variants, including left-bound, right-bound, and search-on-answer patterns
• Binary Search (LeetCode 704): The Foundation - The standard binary search template that this problem builds on