Search Insert Position

• Difficulty: Easy
• Topics: Array, Binary Search
• Link: https://leetcode.com/problems/search-insert-position/

Problem Description

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 <= 104
• -104 <= nums[i] <= 104
• nums contains distinct values sorted in ascending order.
• -104 <= target <= 104

Solution

Search Insert Position - Comprehensive Solution

1. Problem Deconstruction (500+ words)

Rewrite the Problem

1. Technical Version

Given a sorted array nums of length n where nums[i] ∈ ℤ, nums[i] ≠ nums[j] for all i ≠ j, and nums is sorted in strictly ascending order (nums[0] < nums[1] < ... < nums[n-1]), find the smallest index i ∈ [0, n] such that nums[i] ≥ target. Formally:

• If ∃ k ∈ [0, n-1] such that nums[k] = target, return k
• Else, return min{i ∈ [0, n] | nums[i] > target}, with the convention that nums[n] = +∞

The algorithm must achieve O(log n) time complexity, requiring binary search due to the logarithmic constraint.

2. Beginner Version

You have a list of numbers arranged from smallest to largest with no repeating numbers. You’re given a target number. Your task is to find where this number belongs in the list:

• If the number is already in the list, tell me its position (index starting from 0)
• If the number is NOT in the list, tell me the position where you would insert it to keep the list sorted

You must solve this efficiently without checking every single number in the list.

3. Mathematical Version

Let S = {x₀, x₁, ..., xₙ₋₁} be a strictly increasing sequence of distinct integers. For a given integer t, define:

$$f(S, t) = \begin{cases} k & \text{if } \exists k \in [0, n-1] \text{ such that } x_k = t \\ \min\{i \in [0, n] \mid x_i > t\} & \text{otherwise} \end{cases}$$

Equivalently, f(S, t) = |{x ∈ S : x < t}| (the count of elements strictly less than t), which follows from the distinctness and ordering properties.

Constraint Analysis

1. 1 <= nums.length <= 10⁴

   • Limitation: This upper bound prohibits O(n²) algorithms but permits O(n log n) and O(n). However, the O(log n) requirement is stricter.
   • Edge Cases:
     • Minimum length 1: The algorithm must handle single-element arrays correctly.
     • Maximum length 10,000: Binary search requires at most ⌈log₂(10000)⌉ = 14 iterations, well within limits.
   • Implication: Recursive binary search depth is safe (max call stack depth ~14).

2. -10⁴ <= nums[i] <= 10⁴

   • Limitation: Values fit within 16-bit signed integer range. No overflow concerns in Python, but in languages with fixed-width integers, intermediate calculations need care.
   • Edge Cases:
     • Negative values: Algorithm must handle negative targets and array elements.
     • Boundary values: -10⁴ and 10⁴ as extremes.
   • Implication: Comparison operations are O(1) regardless of value magnitude.

3. nums contains distinct values sorted in ascending order

   • Critical Property: Strict monotonicity (nums[i] < nums[i+1] for all i) enables deterministic binary search.
   • Edge Cases:
     • No duplicates simplifies the “first occurrence” concern.
     • Guarantees that if target exists, it’s at exactly one index.
   • Implication: Standard binary search modifications aren’t needed for duplicate handling.

4. -10⁴ <= target <= 10⁴

   • Limitation: Target within same range as array elements.
   • Edge Cases:
     • Target smaller than all elements: Insert at index 0.
     • Target larger than all elements: Insert at index n.
     • Target equal to an element: Exact match.
   • Implication: No need for special handling of out-of-range targets beyond the array bounds.

Hidden Edge Cases Derived from Constraints:

• Single-element array with target: equal, less than, or greater than the element.
• Two-element array testing all relative positions.
• Target equal to first/last element.
• Target between consecutive elements.
• Empty array (though prohibited by constraints, good to consider for generalization).

2. Intuition Scaffolding

Generate 3 Analogies

1. Real-World Metaphor - Library Book Shelving

Imagine you’re a librarian with books arranged by call number in strictly increasing order on a shelf. A new book arrives with call number T. You need to find where it goes:

• If a book with exactly call number T exists, note its position.
• If not, find the gap between two books where T would fit (after a book with number < T and before a book with number > T). Instead of checking every book (linear scan), you use the library’s catalog system that lets you jump to the middle shelf, then recursively halve your search space—this is binary search.

2. Gaming Analogy - RPG Level Progression

In a role-playing game, you have unlocked levels with difficulty scores [10, 20, 30, 40]. Your character’s current skill level is T. You want to:

• Find the level that exactly matches your skill (to play comfortably).
• If no exact match, find the next hardest level you should attempt. The game’s level selection uses a “magic compass” that points to the middle level, then based on whether you’re over/under-leveled, eliminates half the levels—this is O(log n) progression.

3. Mathematical Analogy - Root Finding on Step Function

Consider the function f(i) = nums[i] - target defined on discrete indices i. This function is:

• Negative where nums[i] < target
• Zero where nums[i] = target (if exists)
• Positive where nums[i] > target

Finding the insertion position is equivalent to finding the smallest i where f(i) ≥ 0. This is like finding the “root” of a non-decreasing step function, which can be solved via binary search on the domain.

Common Pitfalls Section

1. Off-by-One Errors in Binary Search

   • Wrong: Using while left < right but returning right incorrectly.
   • Why: Different loop conditions lead to different termination states.
   • Example: For nums=[1,3,5,7], target=6, wrong bounds might return index 2 instead of 3.

2. Infinite Loop with Mid Calculation

   • Wrong: mid = (left + right) // 2 with left = mid (not mid + 1) in some cases.
   • Why: When left and right differ by 1, mid equals left, causing stagnation.
   • Fix: Always ensure interval shrinks: left = mid + 1 or right = mid - 1.

3. Missing Early Termination on Exact Match

   • Wrong: Continuing binary search even after finding nums[mid] == target.
   • Why: Wastes computation; insertion index differs from exact match index.
   • Fix: Return mid immediately when nums[mid] == target.

4. Incorrect Handling of Empty Search Space

   • Wrong: Returning -1 or other sentinel when target not found.
   • Why: Problem requires insertion index, not “not found” indicator.
   • Fix: Return left after loop termination (invariant: left is insertion point).

5. Assuming Target Always in Bounds

   • Wrong: Not testing target < nums[0] or target > nums[-1].
   • Why: Binary search implementations might assume target within array range.
   • Fix: Let binary search handle naturally; final left will be 0 or n.

6. Using Linear Scan Despite O(log n) Requirement

   • Wrong: Simple for-loop checking nums[i] >= target.
   • Why: O(n) violates requirement, though acceptable for small n.
   • Fix: Must implement binary search.

7. Confusing Insertion Index with Search Index

   • Wrong: Returning index where target should be even when target exists.
   • Why: Misreading problem as “always return insertion index”.
   • Fix: Check for equality first, return that index.

3. Approach Encyclopedia

Approach 1: Brute Force Linear Scan

Pseudocode

def searchInsert(nums, target):
    # Iterate through each position
    for i in range(len(nums)):
        # First position where element >= target
        if nums[i] >= target:
            return i
    # If all elements < target, insert at end
    return len(nums)

Complexity Proof

• Time: Let n = len(nums). In worst case (target > all elements), loop runs n times. Each iteration does one comparison → n comparisons. Thus T(n) = n ∈ O(n).
• Space: Uses only constant extra variables (i) → S(n) = 1 ∈ O(1).

Visualization

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

Step i=0: nums[0]=1 < 6 → continue
      i=1: nums[1]=3 < 6 → continue  
      i=2: nums[2]=5 < 6 → continue
      i=3: nums[3]=7 ≥ 6 → return 3

Index:   0   1   2   3
Value:   1   3   5   7
                  ↑
                6 > 5 but < 7, so insert at index 3

Approach 2: Binary Search (Iterative Standard)

Pseudocode

def searchInsert(nums, target):
    left, right = 0, len(nums) - 1
    
    while left <= right:
        mid = left + (right - left) // 2  # Avoid overflow
        
        if nums[mid] == target:
            return mid          # Exact match
        elif nums[mid] < target:
            left = mid + 1      # Search right half
        else:  # nums[mid] > target
            right = mid - 1     # Search left half
    
    return left  # Insertion point when not found

Complexity Proof

• Time: Each iteration halves search space: n → n/2 → n/4 → ... → 1. Number of iterations k satisfies n/2^k ≤ 1 ⇒ k ≥ log₂n. Thus T(n) = O(log n).
• Space: Three integer variables (left, right, mid) → S(n) = O(1).

Visualization

nums = [1, 3, 5, 7, 9, 11], target = 8

Initial: left=0, right=5
[1, 3, 5, 7, 9, 11]
 L        M        R  (mid=2, nums[2]=5 < 8)

Step 1: left=3, right=5
[1, 3, 5, 7, 9, 11]
          L  M   R    (mid=4, nums[4]=9 > 8)

Step 2: left=3, right=3
[1, 3, 5, 7, 9, 11]
          L/M R       (mid=3, nums[3]=7 < 8)

Step 3: left=4, right=3 → loop ends
Return left=4 (insert between 7 and 9)

Approach 3: Binary Search (Lower Bound Variant)

Pseudocode

def searchInsert(nums, target):
    left, right = 0, len(nums)  # Note: right is exclusive
    
    while left < right:
        mid = left + (right - left) // 2
        
        if nums[mid] < target:
            left = mid + 1
        else:  # nums[mid] >= target
            right = mid
    
    return left  # left == right, insertion point

Complexity Proof

• Time: Same halving principle → O(log n).
• Space: O(1).
• Key Difference: This finds first position where nums[i] ≥ target directly (lower bound), without early exit on equality. Useful if duplicates existed (though here they don’t).

Approach 4: Recursive Binary Search

Pseudocode

def searchInsert(nums, target):
    def binary_search(l, r):
        if l > r:
            return l  # Base case: insertion point
        
        mid = (l + r) // 2
        
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            return binary_search(mid + 1, r)
        else:
            return binary_search(l, mid - 1)
    
    return binary_search(0, len(nums) - 1)

Complexity Proof

• Time: O(log n) from recurrence T(n) = T(n/2) + O(1) ⇒ by Master Theorem, Θ(log n).
• Space: Recursion depth O(log n) from call stack.

4. Code Deep Dive

Optimal Solution: Iterative Binary Search

def searchInsert(nums, target):
    # Initialize search boundaries
    left = 0                     # Smallest possible index
    right = len(nums) - 1        # Largest possible index
    
    # Continue while search interval is valid
    while left <= right:
        # Calculate middle index - prevents integer overflow
        # Equivalent to (left + right) // 2 but safe for large numbers
        mid = left + (right - left) // 2
        
        # Case 1: Exact match found
        if nums[mid] == target:
            return mid           # Return immediately, no insertion needed
        
        # Case 2: Target is in right half
        # Since array is sorted, if middle element is smaller,
        # target must be to the right (if present)
        elif nums[mid] < target:
            left = mid + 1       # Discard left half including mid
        
        # Case 3: Target is in left half
        # Middle element is larger, so target must be left (if present)
        else:  # nums[mid] > target
            right = mid - 1      # Discard right half including mid
    
    # Loop terminated: target not found
    # At this point, left > right
    # The insertion point is left because:
    # - All indices < left have values < target
    # - All indices > right have values > target
    # - left is the smallest index where target could be inserted
    return left

Line-by-Line Annotations

1. left = 0 - Sets lower bound to first valid index. This represents the current candidate for insertion position if target is smaller than all elements.

2. right = len(nums) - 1 - Sets upper bound to last valid index. This covers the entire array’s search space initially.

3. while left <= right: - Loop continues while there’s at least one element to examine. The <= is crucial: when left == right, we still need to check that single element.

4. mid = left + (right - left) // 2 - Computes middle index without overflow risk. In Python, overflow isn’t an issue, but this is idiomatic for binary search across languages.

5. if nums[mid] == target: - Check for exact match. If found, return immediately since we have the exact index.

6. elif nums[mid] < target: - Target must be in the right half. Update left = mid + 1 because:

   • nums[mid] is too small
   • If target exists, it must be at index > mid
   • If target doesn’t exist, insertion point is > mid

7. else: - Implies nums[mid] > target. Target must be in left half. Update right = mid - 1 because:

   • nums[mid] is too large
   • If target exists, it must be at index < mid
   • If target doesn’t exist, insertion point is ≤ mid

8. return left - After loop termination (left > right), left points to the insertion position. This works because:

   • Invariant: At each step, insertion index is in [left, right+1]
   • When loop ends, left = right + 1
   • All elements at indices < left are < target
   • All elements at indices > right are > target
   • Thus left is the correct insertion index

Edge Case Handling

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

Iteration 1: left=0, right=3, mid=1 → nums[1]=3 < 5 → left=2
Iteration 2: left=2, right=3, mid=2 → nums[2]=5 == 5 → return 2

Code Path: Hits exact match at line 5, returns immediately.

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

Iteration 1: left=0, right=3, mid=1 → nums[1]=3 > 2 → right=0
Iteration 2: left=0, right=0, mid=0 → nums[0]=1 < 2 → left=1
Iteration 3: left=1, right=0 → loop exits, return left=1

Code Path: Never finds exact match, loop terminates when search space exhausted, returns left=1.

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

Iteration 1: left=0, right=3, mid=1 → nums[1]=3 < 7 → left=2
Iteration 2: left=2, right=3, mid=2 → nums[2]=5 < 7 → left=3
Iteration 3: left=3, right=3, mid=3 → nums[3]=6 < 7 → left=4
Iteration 4: left=4, right=3 → loop exits, return left=4

Code Path: Target larger than all elements, left increments until it exceeds right, returns len(nums).

Single Element Array: nums = [5], target = 2

Iteration 1: left=0, right=0, mid=0 → nums[0]=5 > 2 → right=-1
Loop exits, return left=0

Target Smaller Than All: nums = [10,20,30], target = 5

Iteration 1: left=0, right=2, mid=1 → nums[1]=20 > 5 → right=0
Iteration 2: left=0, right=0, mid=0 → nums[0]=10 > 5 → right=-1
Loop exits, return left=0

5. Complexity War Room

Hardware-Aware Analysis

For n = 10,000 (maximum constraint):

• Binary Search Iterations: ⌈log₂(10000)⌉ = 14 iterations maximum
• Operations per Iteration: ~6 operations (arithmetic, comparison, assignment)
• Total Operations: ~84 primitive operations
• Memory Usage: 3 integers × 4-8 bytes = 12-24 bytes
• Cache Behavior: Excellent - all variables fit in CPU registers (L1 cache)
• Performance: On a 3GHz CPU, ~28 nanoseconds (assuming 3 cycles per operation)

Comparison with Linear Scan:

• Linear scan: 10,000 comparisons = ~30,000 operations
• Binary search: 84 operations
• Speedup: ~357× faster

Industry Comparison Table

Approach	Time Complexity	Space Complexity	Readability	Interview Viability	Use Case
Brute Force Linear	O(n)	O(1)	10/10 (Trivial)	❌ Fails O(log n) requirement	Educational only
Binary Search (Iterative)	O(log n)	O(1)	8/10 (Some edge cases)	✅ Gold Standard	Production code
Binary Search (Recursive)	O(log n)	O(log n) stack	7/10 (Recursion overhead)	⚠️ Acceptable if explained	Teaching recursion
Built-in bisect	O(log n)	O(1)	10/10 (Pythonic)	⚠️ May need manual implementation	Real-world Python
Binary Search (Lower Bound)	O(log n)	O(1)	9/10 (Elegant)	✅ Excellent alternative	Generic search

Interview Notes:

• Iterative binary search is preferred (avoids stack overflow for large n)
• Must mention early termination on exact match vs insertion index return
• Always discuss the left return invariant

6. Pro Mode Extras

Variants Section

Variant 1: Search Insert with Duplicates

def searchInsertDuplicate(nums, target):
    """Returns first index where target appears or should be inserted"""
    left, right = 0, len(nums)
    while left < right:
        mid = left + (right - left) // 2
        if nums[mid] < target:
            left = mid + 1
        else:
            right = mid
    return left

Change: No early return on equality; finds first occurrence.

Variant 2: Search in Rotated Sorted Array (LeetCode 33)

def searchRotated(nums, target):
    left, right = 0, len(nums)-1
    while left <= right:
        mid = left + (right-left)//2
        if nums[mid] == target:
            return mid
        # Left half is sorted
        if nums[left] <= nums[mid]:
            if nums[left] <= target < nums[mid]:
                right = mid-1
            else:
                left = mid+1
        # Right half is sorted
        else:
            if nums[mid] < target <= nums[right]:
                left = mid+1
            else:
                right = mid-1
    return -1  # Not found

Complexity: Still O(log n) but with more conditions.

Variant 3: Find First and Last Position (LeetCode 34)

def searchRange(nums, target):
    def findLeft():
        left, right = 0, len(nums)
        while left < right:
            mid = left + (right-left)//2
            if nums[mid] < target:
                left = mid+1
            else:
                right = mid
        return left
    
    def findRight():
        left, right = 0, len(nums)
        while left < right:
            mid = left + (right-left)//2
            if nums[mid] <= target:
                left = mid+1
            else:
                right = mid
        return left-1
    
    left_idx = findLeft()
    if left_idx == len(nums) or nums[left_idx] != target:
        return [-1, -1]
    return [left_idx, findRight()]

Extension: Two binary searches for left and right bounds.

Variant 4: Binary Search on Answer Space

def mySqrt(x):
    """Find integer square root using binary search on [0, x]"""
    if x < 2:
        return x
    left, right = 0, x
    while left <= right:
        mid = left + (right-left)//2
        if mid*mid == x:
            return mid
        elif mid*mid < x:
            left = mid+1
        else:
            right = mid-1
    return right  # Floor of square root

Concept: Binary search not on array but on possible answer range.

Interview Cheat Sheet

Binary Search Template (Memorize)

def binary_search_template(nums, target):
    left, right = 0, len(nums)-1  # Inclusive bounds
    
    while left <= right:
        mid = left + (right-left)//2
        
        if nums[mid] == target:
            return mid          # Exact match
        elif nums[mid] < target:
            left = mid + 1      # Search right
        else:
            right = mid - 1     # Search left
    
    return left  # Insertion point

Key Points to Mention

1. Always start with constraints analysis: “Given n ≤ 10⁴, O(n) is acceptable but O(log n) is required.”
2. State invariant: “I’ll maintain that the insertion point is in [left, right+1].”
3. Explain termination: “When left > right, all elements < target are before left, all > target are after right.”
4. Test edge cases verbally:
   • Empty array (if allowed)
   • Single element
   • Target at boundaries
   • Target not present
5. Complexity justification: “Each iteration halves search space → O(log n) time, O(1) space.”

Common Interview Questions

• Q: “What if there were duplicates?”
  • A: “We’d modify to find first occurrence by not early returning, using lower_bound approach.”
• Q: “Why return left after loop?”
  • A: “It’s the insertion point invariant: after termination, left is where target belongs.”
• Q: “Can you implement recursively?”
  • A: “Yes, but iterative avoids O(log n) stack space and is generally preferred.”

Performance Optimization Notes

• For extremely large arrays, consider:
  • Cache-efficient binary search (Eytzinger layout)
  • Branch prediction-friendly code
  • For n < 50, linear scan might be faster due to constant factors

This comprehensive solution covers theoretical foundations, practical implementation, and professional considerations for the Search Insert Position problem.