Problem Description

You are given a sorted array of distinct integers and a target value. Your task is to find where the target value should be placed in the array to maintain the sorted order.

If the target value already exists in the array, return its index. If the target value doesn't exist, return the index where it would be inserted to keep the array sorted.

For example:

• If nums = [1, 3, 5, 6] and target = 5, the function should return 2 because 5 exists at index 2
• If nums = [1, 3, 5, 6] and target = 2, the function should return 1 because 2 would be inserted at index 1 to maintain sorted order
• If nums = [1, 3, 5, 6] and target = 7, the function should return 4 because 7 would be inserted at the end

The algorithm must have O(log n) runtime complexity, which means you need to use binary search rather than a linear scan through the array.

The solution uses binary search to efficiently find the insertion position. It maintains two pointers l (left) and r (right) to define the search range. In each iteration, it calculates the middle index and compares nums[mid] with the target. If nums[mid] >= target, it means the target should be inserted at or before the middle position, so the search continues in the left half. Otherwise, the search continues in the right half. When the loop ends, l points to the correct insertion position.

Intuition

Since we need O(log n) complexity and the array is sorted, binary search is the natural choice. The key insight is that we're not just searching for an exact match - we're looking for the correct insertion position.

Think of binary search as repeatedly dividing the search space in half. At each step, we compare the middle element with our target. If nums[mid] >= target, we know the target belongs somewhere in the left half (including possibly at the current middle position). If nums[mid] < target, the target must go somewhere in the right half.

The clever part is recognizing that we want to find the leftmost position where we could insert the target. This is why when nums[mid] >= target, we set r = mid (not mid - 1). We're saying "the answer could be at mid or somewhere to its left." When nums[mid] < target, we know for certain the answer is to the right of mid, so we set l = mid + 1.

By the time our search window shrinks to nothing (l >= r), l will be pointing exactly where the target should go:

• If the target exists, l points to its position
• If the target doesn't exist, l points to where it would maintain sorted order

This approach elegantly handles both cases (element exists or doesn't exist) with the same logic, avoiding the need for special case handling.

Learn more about Binary Search patterns.

Solution Approach

The implementation uses binary search with a two-pointer approach. Here's how the algorithm works step by step:

Initial Setup:

• Initialize l = 0 (left boundary) and r = len(nums) (right boundary)
• Note that r is set to the array length, not len(nums) - 1, allowing us to handle insertion at the end of the array

Binary Search Loop: The loop continues while l < r:

1. Calculate the middle index: mid = (l + r) >> 1

   • The >> 1 operation is a bitwise right shift, equivalent to integer division by 2
   • This efficiently finds the midpoint of our current search range

2. Compare nums[mid] with target:

   • If nums[mid] >= target: Set r = mid
     • This means the target should be at position mid or somewhere to its left
     • We keep mid in our search range because it could be the answer
   • If nums[mid] < target: Set l = mid + 1
     • The target must be inserted after position mid
     • We can safely exclude mid from our search range

Loop Termination: When l >= r, the search window has converged to a single position. At this point, l represents:

• The index of the target if it exists in the array
• The index where the target should be inserted if it doesn't exist

Return Value: The function returns l, which is the correct insertion position.

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

• Initial: l = 0, r = 4
• Iteration 1: mid = 2, nums[2] = 5 >= 2, so r = 2
• Iteration 2: mid = 1, nums[1] = 3 >= 2, so r = 1
• Iteration 3: mid = 0, nums[0] = 1 < 2, so l = 1
• Loop ends as l == r == 1
• Returns 1, the correct insertion position

Example Walkthrough

Let's walk through finding the insertion position for target = 4 in the array nums = [1, 3, 5, 7, 9].

Initial State:

• Array: [1, 3, 5, 7, 9]
• Target: 4 (doesn't exist, should go between 3 and 5)
• l = 0, r = 5 (array length)

Iteration 1:

• Calculate mid = (0 + 5) >> 1 = 2
• Check nums[2] = 5
• Since 5 >= 4, the target belongs at position 2 or to its left
• Update: r = 2
• Search range: [1, 3, 5] (indices 0-1, with 2 as potential answer)

Iteration 2:

• Calculate mid = (0 + 2) >> 1 = 1
• Check nums[1] = 3
• Since 3 < 4, the target must go after position 1
• Update: l = 2
• Search range narrows to index 2

Termination:

• Now l = 2 and r = 2, so l >= r
• Loop ends
• Return l = 2

Verification: Inserting 4 at index 2 would give us [1, 3, 4, 5, 7, 9], which maintains sorted order. The algorithm correctly identified that 4 should be placed where 5 currently is, shifting 5 and subsequent elements to the right.

Key Insight: Notice how the algorithm naturally converges to the correct position. When we find an element greater than or equal to our target (5 in this case), we keep it as a candidate position. When we find an element less than our target (3 in this case), we know the answer must be after it. The two pointers eventually meet at the exact insertion point.

Solution Implementation

Time and Space Complexity

The time complexity is O(log n), where n is the length of the array nums. This is because the algorithm uses binary search, which divides the search space in half with each iteration. The while loop continues until l < r is false, and in each iteration, we either set r = mid or l = mid + 1, effectively halving the search range. Therefore, the maximum number of iterations is log₂(n).

The space complexity is O(1) as the algorithm only uses a constant amount of extra space. The variables l, r, and mid are the only additional space used, regardless of the input size. No recursive calls are made, and no additional data structures are created that depend on the input size.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Right Boundary Initialization

One of the most common mistakes is initializing right = len(nums) - 1 instead of right = len(nums). This seems intuitive since array indices go from 0 to len(nums) - 1, but it causes problems when the target should be inserted at the end of the array.

Incorrect Implementation:

def searchInsert(self, nums: List[int], target: int) -> int:
    left, right = 0, len(nums) - 1  # Wrong!
  
    while left < right:
        mid = (left + right) >> 1
        if nums[mid] >= target:
            right = mid
        else:
            left = mid + 1
  
    return left

Problem: When target = 7 and nums = [1, 3, 5, 6], this returns index 3 instead of 4. The algorithm never considers position 4 as a valid insertion point.

Solution: Always use right = len(nums) to include the position after the last element as a valid insertion point.

2. Infinite Loop with Wrong Update Logic

Another pitfall occurs when using left <= right as the loop condition with incorrect pointer updates.

Incorrect Implementation:

def searchInsert(self, nums: List[int], target: int) -> int:
    left, right = 0, len(nums) - 1
  
    while left <= right:  # Different condition
        mid = (left + right) >> 1
        if nums[mid] >= target:
            right = mid  # This can cause infinite loop!
        else:
            left = mid + 1
  
    return left

Problem: When left == right, setting right = mid doesn't change the search range, causing an infinite loop.

Solution: Either use left < right with right = mid, or use left <= right with right = mid - 1.

3. Integer Overflow in Mid Calculation

In languages with fixed integer sizes (like Java or C++), calculating mid = (left + right) / 2 can cause integer overflow when left + right exceeds the maximum integer value.

Safe Calculation Methods:

# Method 1: Use subtraction to avoid overflow
mid = left + (right - left) // 2

# Method 2: Bitwise operation (works in Python)
mid = (left + right) >> 1

# Method 3: Python's integer division (no overflow in Python)
mid = (left + right) // 2

4. Handling Edge Cases Incorrectly

Failing to handle empty arrays or single-element arrays properly.

Robust Implementation with Edge Case Handling:

def searchInsert(self, nums: List[int], target: int) -> int:
    # Handle empty array
    if not nums:
        return 0
  
    # Standard binary search
    left, right = 0, len(nums)
  
    while left < right:
        mid = (left + right) >> 1
        if nums[mid] >= target:
            right = mid
        else:
            left = mid + 1
  
    return left

Note: The original solution actually handles empty arrays correctly since when nums = [], left = 0 and right = 0, so the loop doesn't execute and returns 0, which is correct.