LeetCode #35 — Easy

Search Insert
Position

A complete visual walkthrough of binary search — finding a target or where it belongs in a sorted array.

Patterns Used
🔍Modified Binary Search→

Roadmap

  1. The Brute Force — Linear Scan
  2. The Core Insight — Why lo Is the Answer
  3. Walkthrough — Step by Step
  4. Edge Cases
  5. Full Annotated Code
  6. Interactive Demo
  7. Complexity Analysis
Step 01

The Brute Force — Linear Scan

The simplest approach: scan left to right until you find the target or the first element greater than the target. That index is your answer.

Linear Scan Example

Array: [1, 3, 5, 6], target = 5

index
0
1
2
3
nums
1
3
5
6
Found target 5 at index 2 → return 2

Insert Case

Array: [1, 3, 5, 6], target = 2

nums
1
3
5
6
3 > 2, first element bigger than target at index 1 → return 1

This works, but it's O(n) — we check every element in the worst case. Since the array is sorted, we can do much better.

// Brute force: O(n)
for (int i = 0; i < nums.length; i++) {
    if (nums[i] >= target) return i;
}
return nums.length;
Step 02

The Core Insight — Why lo Is the Answer

Standard binary search narrows a range [lo, hi] until lo > hi. The beautiful insight for this problem:

The Invariant

When the loop ends without finding the target, lo always points to the correct insertion position. Here's why:

nums[mid] < target
Target belongs after mid, so lo = mid + 1 moves right past elements that are too small.
nums[mid] > target
Target belongs before mid, so hi = mid - 1 moves left past elements that are too large.

When lo crosses hi, lo sits right where the target would be inserted — all elements before lo are smaller, all elements from lo onward are larger.

💡

This is the standard binary search template! The only difference from a "find element" binary search is: instead of returning -1 when not found, we return lo. That single change solves the entire problem.

Step 03

Walkthrough — Step by Step

Let's trace through with nums = [1, 3, 5, 6], target = 2 (insert case):

Iteration 1

lo=0, hi=3, mid=1

nums
1
3
5
6
lo
mid
hi

nums[1] = 3 > target (2) → target is to the left → hi = mid - 1 = 0

Iteration 2

lo=0, hi=0, mid=0

nums
1
3
5
6
lo/mid/hi

nums[0] = 1 < target (2) → target is to the right → lo = mid + 1 = 1

Loop Ends: lo=1 > hi=0

nums
1
?
3
5
6

Return lo = 1 — insert 2 at index 1, between 1 and 3. The array becomes [1, 2, 3, 5, 6].

Step 04

Edge Cases

Binary search handles these naturally — no special code needed:

Step 05

Full Annotated Code

class Solution {
    public int searchInsert(int[] nums, int target) {

        int lo = 0, hi = nums.length - 1;

        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;   // avoids integer overflow

            if (nums[mid] == target) {
                return mid;                  // found it!
            } else if (nums[mid] < target) {
                lo = mid + 1;                // search right half
            } else {
                hi = mid - 1;                // search left half
            }
        }

        return lo;  // not found — lo is the insert position
    }
}
⚡

Why lo + (hi - lo) / 2 instead of (lo + hi) / 2? When lo and hi are both large, their sum can overflow a 32-bit integer. The subtraction form avoids this. Functionally identical, but safer.

Step 06

Interactive Demo

Try different arrays and targets. Step through each binary search iteration to see lo, hi, and mid move.

Binary Search Visualizer



Step 07

Complexity Analysis

Time
O(log n)
Space
O(1)

Each iteration halves the search space. For an array of length n, we do at most log₂(n) iterations. We use only a few integer variables — no extra data structures.

📝

Concrete numbers: For n = 1,000,000 elements, binary search takes at most 20 comparisons (since 2^20 ≈ 1M). The brute force would need up to 1,000,000 comparisons. That is the power of logarithmic time.