55. Search Insert Position

🔗 LeetCode Problem: 35. Search Insert Position
📊 Difficulty: Easy
🏷️ Topics: Array, Binary Search

Problem Statement

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.

Example 1:

Input: nums = [1,3,5,6], target = 5
Output: 2

Example 2:

Input: nums = [1,3,5,6], target = 2
Output: 1

Example 3:

Input: nums = [1,3,5,6], target = 7
Output: 4

Constraints: - 1 <= nums.length <= 10^4 - -10^4 <= nums[i] <= 10^4 - nums contains distinct values sorted in ascending order - -10^4 <= target <= 10^4

🎨 Visual Understanding

The Problem Visualized

nums = [1, 3, 5, 6], target = 5

Array: [1, 3, 5, 6]
Index:  0  1  2  3

Target 5 is found at index 2
Answer: 2

nums = [1, 3, 5, 6], target = 2

Array: [1, 3, 5, 6]
Index:  0  1  2  3
        ↑  ← insert here

Target 2 not found.
Should be inserted between 1 and 3.
Answer: 1 (index where it should be)

After insertion: [1, 2, 3, 5, 6]

nums = [1, 3, 5, 6], target = 7

Array: [1, 3, 5, 6]
Index:  0  1  2  3  ← insert here

Target 7 not found.
Should be inserted at end.
Answer: 4

After insertion: [1, 3, 5, 6, 7]

🚨 CRITICAL INSIGHT - Why Binary Search Works

The Key Property:

After binary search loop ends:
  left pointer = insertion position!

Why?
  Loop maintains invariant:
    All elements at indices < left are < target
    All elements at indices >= left are >= target

  So left is EXACTLY where target belongs!

Example trace: nums = [1, 3, 5, 6], target = 2

Initial: left = 0, right = 3
         [1, 3, 5, 6]
          ↑        ↑
        left     right

Step 1: mid = 1, nums[1] = 3
        3 > 2, so target is in left half
        right = mid - 1 = 0
        [1, 3, 5, 6]
         ↑
       left/right

Step 2: mid = 0, nums[0] = 1
        1 < 2, so target is in right half
        left = mid + 1 = 1
        [1, 3, 5, 6]
            ↑
          left

Loop ends (left > right)
left = 1 = insertion position! ✓

The Binary Search Invariant

Throughout the search:
  All nums[i] where i < left: nums[i] < target
  All nums[i] where i > right: nums[i] > target

When loop ends (left > right):
  left is the smallest index where nums[i] >= target
  = insertion position!

This works whether target exists or not:
  - If exists: we return index during search
  - If not: left is where it should be inserted

🎯 Approach 1: Linear Search (Brute Force)

The Most Natural Thinking 💭

Core Logic:

Walk through array from left to right.
Return index of first element >= target.
If no such element, return array length.

Implementation

public int searchInsert(int[] nums, int target) {
    // Scan from left to right
    for (int i = 0; i < nums.length; i++) {
        // Found target or found insertion position
        if (nums[i] >= target) {
            return i;
        }
    }

    // Target is larger than all elements
    // Should be inserted at end
    return nums.length;
}

⏰ Time: O(n) - Single pass through array
💾 Space: O(1) - Only variables

Why This Works:

We stop at first element >= target:
  - If nums[i] == target: found it!
  - If nums[i] > target: target should go before nums[i]

If we reach end: target > all elements
  Should be inserted at end

❌ Problem: Doesn't meet O(log n) requirement!

🎯 Approach 2: Binary Search (Optimal) ⭐

Better Approach 💡

🧠 The Core Insight

Array is sorted → Use Binary Search!

Key insight: We're looking for "lower bound"
  = smallest index where nums[i] >= target

Binary search naturally gives us this:
  When loop ends, left = lower bound

The Binary Search Template:

Standard binary search with TWO outcomes:
1. Target found during search → return mid
2. Loop ends → return left (insertion position)

Why left and not right?
  After loop: left = right + 1
  left points to first element >= target
  right points to last element < target

  Insertion position = left!

Implementation

public int searchInsert(int[] nums, int target) {
    int left = 0;
    int right = nums.length - 1;

    while (left <= right) {
        // Safe mid calculation (prevents overflow)
        int mid = left + (right - left) / 2;

        // Case 1: Target found
        if (nums[mid] == target) {
            return mid;
        }

        // Case 2: Target in right half
        if (nums[mid] < target) {
            left = mid + 1;
        } 
        // Case 3: Target in left half
        else {
            right = mid - 1;
        }
    }

    // Loop ended: target not found
    // left is the insertion position
    return left;
}

⏰ Time: O(log n) - Binary search
💾 Space: O(1) - Only pointers

🔍 Dry Run

Example 1: nums = [1, 3, 5, 6], target = 5

Initial: left = 0, right = 3
         [1, 3, 5, 6]
          ↑        ↑
        left     right

Iteration 1:
  mid = 0 + (3 - 0) / 2 = 1
  nums[1] = 3
  3 < 5 → target in right half
  left = 2
  [1, 3, 5, 6]
           ↑  ↑
         left right

Iteration 2:
  mid = 2 + (3 - 2) / 2 = 2
  nums[2] = 5
  5 == 5 → FOUND!
  return 2 ✓

Example 2: nums = [1, 3, 5, 6], target = 2

Initial: left = 0, right = 3
         [1, 3, 5, 6]
          ↑        ↑
        left     right

Iteration 1:
  mid = 0 + (3 - 0) / 2 = 1
  nums[1] = 3
  3 > 2 → target in left half
  right = 0
  [1, 3, 5, 6]
   ↑
 left/right

Iteration 2:
  mid = 0 + (0 - 0) / 2 = 0
  nums[0] = 1
  1 < 2 → target in right half
  left = 1
  [1, 3, 5, 6]
      ↑
    left

Loop ends (left > right)
return left = 1 ✓

Meaning: Insert at index 1
Result: [1, 2, 3, 5, 6]

Example 3: nums = [1, 3, 5, 6], target = 7

Initial: left = 0, right = 3
         [1, 3, 5, 6]
          ↑        ↑
        left     right

Iteration 1:
  mid = 0 + (3 - 0) / 2 = 1
  nums[1] = 3
  3 < 7 → target in right half
  left = 2
  [1, 3, 5, 6]
           ↑  ↑
         left right

Iteration 2:
  mid = 2 + (3 - 2) / 2 = 2
  nums[2] = 5
  5 < 7 → target in right half
  left = 3
  [1, 3, 5, 6]
              ↑
            left/right

Iteration 3:
  mid = 3 + (3 - 3) / 2 = 3
  nums[3] = 6
  6 < 7 → target in right half
  left = 4
  [1, 3, 5, 6]
               ↑
             left

Loop ends (left > right)
return left = 4 ✓

Meaning: Insert at end
Result: [1, 3, 5, 6, 7]

Example 4: nums = [1, 3, 5, 6], target = 0

Initial: left = 0, right = 3
         [1, 3, 5, 6]
          ↑        ↑
        left     right

Iteration 1:
  mid = 0 + (3 - 0) / 2 = 1
  nums[1] = 3
  3 > 0 → target in left half
  right = 0
  [1, 3, 5, 6]
   ↑
 left/right

Iteration 2:
  mid = 0 + (0 - 0) / 2 = 0
  nums[0] = 1
  1 > 0 → target in left half
  right = -1
  [1, 3, 5, 6]
  ↑
left

Loop ends (left > right)
return left = 0 ✓

Meaning: Insert at beginning
Result: [0, 1, 3, 5, 6]

🎯 Why This Works - Deep Dive

The Magic of left Pointer:
═══════════════════════════════════════════════════════════════

After each comparison:
  nums[mid] < target → left = mid + 1
    Meaning: Everything <= mid is too small
    So left moves to first position that MIGHT be >= target

  nums[mid] > target → right = mid - 1
    Meaning: Everything >= mid is too large
    So right moves to last position that MIGHT be < target

When loop ends (left > right):
  All positions < left: too small (< target)
  All positions > right: too large (>= target)

  Since left = right + 1:
    left is the transition point!
    = smallest index where nums[i] >= target
    = insertion position!

Visual:
  [elements < target] [elements >= target]
                      ↑
                    left = insertion point

This works whether target exists or not!

The Lower Bound Concept

This binary search finds "lower bound":
  = smallest index i where nums[i] >= target

If target exists:
  lower bound = its index
  We return during search

If target doesn't exist:
  lower bound = where it should be inserted
  We return after loop

Standard binary search pattern!

⚠️ Common Mistakes to Avoid

Mistake 1: Using (left + right) / 2 for mid

// ❌ WRONG - Can overflow when left + right > Integer.MAX_VALUE
int mid = (left + right) / 2;

// ✓ CORRECT - Safe from overflow
int mid = left + (right - left) / 2;

Why it matters:

If left = 2,000,000,000 and right = 2,000,000,000
left + right = 4,000,000,000 > Integer.MAX_VALUE
Causes integer overflow!

left + (right - left) / 2 is always safe:
2,000,000,000 + (2,000,000,000 - 2,000,000,000) / 2
= 2,000,000,000 + 0 = 2,000,000,000 ✓

Mistake 2: Wrong loop condition

// ❌ WRONG - Misses cases
while (left < right) {
    // ...
}

// ✓ CORRECT - Standard binary search
while (left <= right) {
    // ...
}

Why left <= right?

Consider nums = [5], target = 5

With left < right:
  left = 0, right = 0
  Loop doesn't run! (0 < 0 is false)
  Returns 0 without checking
  Wrong if target != 5!

With left <= right:
  left = 0, right = 0
  Loop runs! (0 <= 0 is true)
  Checks nums[0] == 5
  Correct behavior!

Mistake 3: Not returning left after loop

// ❌ WRONG - Returning -1
while (left <= right) {
    // ...
}
return -1;  // Wrong! Should return insertion position

// ✓ CORRECT - Return left
return left;  // Insertion position

Mistake 4: Off-by-one in pointer updates

// ❌ WRONG - Not moving pointers enough
if (nums[mid] < target) {
    left = mid;  // Infinite loop risk!
}

// ✓ CORRECT - Always ± 1
if (nums[mid] < target) {
    left = mid + 1;
}

Why ± 1 is critical:

Without ± 1:
  [1, 3], target = 2
  left = 0, right = 1
  mid = 0, nums[0] = 1 < 2
  left = mid = 0  (no change!)
  Infinite loop!

With ± 1:
  left = mid + 1 = 1
  Now left = right = 1
  Next iteration finds answer

Mistake 5: Wrong initialization

// ❌ WRONG
int right = nums.length;  // Out of bounds!

// ✓ CORRECT
int right = nums.length - 1;  // Last valid index

🎯 Pattern Recognition

Problem Type: Binary Search - Find Insertion Position
Core Pattern: Lower Bound Binary Search

When to Apply:
✓ Array is sorted
✓ Need to find position (not just existence)
✓ If not found, return where it should be
✓ Requires O(log n) time

Recognition Keywords:
- "Sorted array"
- "Insert position"
- "Index where it would be"
- "O(log n) runtime"
- "Ascending/descending order"

Similar Problems:
- First Bad Version (LC 278)
- Find First and Last Position (LC 34)
- Search in Rotated Sorted Array (LC 33)
- Find Minimum in Rotated Sorted Array (LC 153)
- Find Peak Element (LC 162)

Key Difference from Classic Binary Search:
┌────────────────────────────────────────────┐
│ Classic Binary Search:                     │
│   - Return -1 if not found                 │
│   - Only cares about existence             │
│                                            │
│ Search Insert Position (This Problem):    │
│   - Return insertion position if not found │
│   - left pointer has the answer            │
│   - Never returns -1                       │
└────────────────────────────────────────────┘

The "left = insertion position" is the key insight!

🧠 Interview Strategy

Step 1: "Array is sorted, need O(log n) → Binary Search"
Step 2: "If found, return index. If not, return insertion position"
Step 3: "After binary search loop, left points to insertion position"
Step 4: "Use safe mid calculation: left + (right - left) / 2"
Step 5: "Standard template with left <= right"

Key Points to Mention:
- Recognize sorted array → binary search
- Standard binary search with one modification
- If target found during search, return mid
- If loop ends, return left (not -1)
- Why left? It's the lower bound position
- Safe mid calculation prevents overflow
- Loop condition: left <= right
- Time: O(log n), Space: O(1)
- Handles all edge cases naturally

Why This Approach?
"Since the array is sorted and we need O(log n) time, binary search
is the natural choice. The key insight is that after the binary search
loop ends, the left pointer points to the insertion position. This is
because the loop maintains the invariant that all elements before left
are less than target, and all elements from left onwards are greater
than or equal to target. So whether we find the target or not, left
gives us the answer."

Edge Cases Handled:
✓ Target at beginning
✓ Target at end
✓ Target in middle
✓ Target smaller than all
✓ Target larger than all
✓ Single element array
✓ Target equals element

📝 Quick Revision Notes

🎯 Core Concept:

Binary Search for Insertion Position: Use standard binary search. If found, return mid. If not found, return left (insertion position). After loop ends, left = smallest index where nums[i] >= target.

⚡ Quick Implementation:

class Test {
  public int searchInsert(int[] a, int k) {
    int len = a.length;
    int left = 0;
    int right = len - 1;

    while (left <= right) {
      int mid = left + (right - left) / 2;

      if(a[mid] == k) { // target found
        return mid;
      } else if(a[mid] < k) { // search in right space
        left = mid + 1;
      } else { // search in left space
        right = mid - 1;
      }
    }

    return left; // this is imp
  }

  public static void main(String[] args) {
    Test t = new Test();
    System.out.println(t.searchInsert(new int[] {1,3,5,6}, 1)); // 0
    System.out.println(t.searchInsert(new int[] {1,3,5,6}, 6)); // 3
    System.out.println(t.searchInsert(new int[] {1,3,5,6}, 3)); // 1
    System.out.println(t.searchInsert(new int[] {1,3,5,6}, 0)); // 0
    System.out.println(t.searchInsert(new int[] {1,3,5,6}, 7)); // 4
    System.out.println(t.searchInsert(new int[] {1,3,5,6}, 2)); // 1
  }
}

🔑 Key Insights:

Pattern: Binary Search - Lower Bound
Key Property: After loop, left = insertion position
Why left?: All elements before left are < target
Loop Condition: left <= right (standard)
Mid Calculation: left + (right - left) / 2 (safe from overflow)
Pointer Updates: Always use mid ± 1
Return: mid if found, left if not found
Never returns: -1 (always returns valid position)
Time: O(log n) - Binary search
Space: O(1) - Only pointers

🎪 Memory Aid:

"Left is right! After binary search, left points to where target belongs!"
Think: "Left = Lower bound = Insertion position!"

💡 The Key Insight:

After binary search loop ends:
  left pointer → insertion position
  right pointer → last element < target

Since left = right + 1:
  left is EXACTLY where target should be!

This works whether target exists or not:
  Exists → we return during loop
  Not exists → we return left after loop

⚠️ Critical Details:

1. Loop: while (left <= right)
2. Mid: left + (right - left) / 2
3. Updates: mid ± 1 (never just mid)
4. Return: mid if found, left if not
5. Initialize: right = nums.length - 1
6. Works for: all edge cases naturally

🎯 The Invariant:

Throughout search:
  nums[0..left-1]: all < target
  nums[left..n-1]: all >= target (if loop ends)

When loop ends:
  left = smallest i where nums[i] >= target
  = insertion position!

🔥 Why This Pattern Works:

Binary search maintains:
  Everything explored on left < target
  Everything explored on right >= target

As search space shrinks:
  left moves right toward first >= target
  right moves left toward last < target

When they cross (left > right):
  left is at first >= target
  = where target belongs!

🎪 Visual Memory:

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

[values < 2] | [values >= 2]
     1       |     3  5  6
             ↑
           left = 1 = insertion position!

After loop: left points to transition!

🧪 Edge Cases

Case 1: Single element - target exists

Input: nums = [5], target = 5
Output: 0

Case 2: Single element - target smaller

Input: nums = [5], target = 3
Output: 0 (insert before 5)

Case 3: Single element - target larger

Input: nums = [5], target = 7
Output: 1 (insert after 5)

Case 4: Insert at beginning

Input: nums = [3, 5, 7, 9], target = 1
Output: 0

Case 5: Insert at end

Input: nums = [1, 3, 5, 7], target = 10
Output: 4

Case 6: Insert in middle

Input: nums = [1, 3, 5, 7], target = 4
Output: 2 (between 3 and 5)

Case 7: Target exists in middle

Input: nums = [1, 3, 5, 7, 9], target = 5
Output: 2

Case 8: Two elements

Input: nums = [1, 3], target = 2
Output: 1

Input: nums = [1, 3], target = 0
Output: 0

Input: nums = [1, 3], target = 4
Output: 2

All handled correctly with same code! ✓

First Bad Version (LC 278) - Similar binary search pattern
Find First and Last Position (LC 34) - Extended binary search
Search in Rotated Sorted Array (LC 33) - Modified binary search
Find Peak Element (LC 162) - Binary search on unsorted

Happy practicing! 🎯

Note: This is a fundamental binary search problem! Master the "left = insertion position" concept - it appears in many variations!

55. Search Insert Position

Problem Statement

🎨 Visual Understanding

The Problem Visualized

🚨 CRITICAL INSIGHT - Why Binary Search Works

The Binary Search Invariant

🎯 Approach 1: Linear Search (Brute Force)

The Most Natural Thinking 💭

Implementation

🎯 Approach 2: Binary Search (Optimal) ⭐

Better Approach 💡

Implementation

🔍 Dry Run

🎯 Why This Works - Deep Dive

The Lower Bound Concept

⚠️ Common Mistakes to Avoid

🎯 Pattern Recognition

🧠 Interview Strategy

📝 Quick Revision Notes

🧪 Edge Cases

Related Patterns