Search Insert Position (LC 35)

Pattern: Binary Search (Boundary / Insert Position)
Difficulty: Easy
Key Concept: When the search interval empties, left is the first index where you could insert target while keeping order.

Problem Statement

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

Input: int[] nums (sorted ascending), int target
Output: int — index of target, or insertion index in [0, nums.length]

---

1. Algorithm & Pseudocode

Brute force

for i from 0 to nums.length - 1:
    if nums[i] >= target:
        return i
return nums.length

Optimal (binary search for insertion point)

set left = 0, right = nums.length - 1
while left <= right:
    mid = left + (right - left) / 2
    if nums[mid] == target:
        return mid
    if nums[mid] < target:
        left = mid + 1
    else:
        right = mid - 1
return left   // first index where nums[index] >= target, or n if all smaller

---

2. Step-by-Step Analysis (Beginner-Friendly)

1. Same core loop as “find target”
   If target exists, you return as soon as nums[mid] == target.

2. If target is missing
   When the loop exits, left points to the smallest index such that everything to its left is < target. That is exactly where target should go. If all elements are smaller, left becomes nums.length.

3. Why “when left > right, left IS the insertion position”
   Throughout the loop, left only moves past positions that are too small (nums[mid] < target). So anything before left is confirmed < target. The first slot that is not ruled out as “too small” is left.

4. Foundation for boundary binary search
   Many problems reduce to “find first index i with nums[i] >= target” (lower bound). LC 35 is that pattern in disguise: either you hit equality, or you end with left as that boundary.

---

3. The Dry Run

Array: nums = [1, 3, 5, 6]
Indices: 0 1 2 3

Case A: target = 5 (found)

Step	left	right	mid	nums[mid]	Action
init	0	3	—	—	enter loop
1	0	3	1	3	3 < 5 → left = 2
2	2	3	2	5	5 == 5 → return 2

Result: 2.

Case B: target = 2 (not present; insert at index 1)

Step	left	right	mid	nums[mid]	Action
init	0	3	—	—	enter loop
1	0	3	1	3	3 >= 2 and not equal → right = 0
2	0	0	0	1	1 < 2 → left = 1
3	1	0	—	—	left > right → exit

Result: return left → 1 (between 1 and 3).

---

4. Java Solution

Brute Force

class Solution {
    public int searchInsert(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] >= target) {
                return i;
            }
        }
        return nums.length;
    }
}

Time: O(n). Space: O(1).

Optimal

class Solution {
    public int searchInsert(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                return mid;
            }
            if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return left;
    }
}

Time: O(log n). Space: O(1).

---

5. The “Java vs. Others” Edge

• Arrays.binarySearch: On miss, returns -(insertionPoint) - 1. So insertionPoint = -result - 1 when result < 0. That is exactly the “boundary” this problem wants — useful to know for interviews and libraries.
• C++: std::lower_bound(begin, end, target) returns an iterator to the first element >= target; subtract begin for an index — same idea as final left.
• Boundary template: This problem is the template for “first position where condition becomes true” binary search; master it before harder variants (first/last occurrence, peaks, etc.).

---

6. Complexity Summary

Approach	Time	Space	Notes
Brute Force	O(n)	O(1)	Scans until nums[i] >= target.
Optimal	O(log n)	O(1)	Ends with left = insertion index if not found.