Solution Approach

We use the standard binary search template with first_true_index to track the answer.

Template Structure:

left, right = 0, n - 1
first_true_index = -1

while left <= right:
    mid = (left + right) // 2
    if nums[mid] >= target:  # feasible condition
        first_true_index = mid
        right = mid - 1
    else:
        left = mid + 1

return first_true_index if first_true_index != -1 else n

Feasible Condition: nums[mid] >= target

This finds the first index where the element is greater than or equal to the target.

Algorithm Steps:

1. Initialize left = 0, right = n - 1, and first_true_index = -1

2. While left <= right:

   • Calculate mid = (left + right) // 2
   • If nums[mid] >= target: record mid as potential answer, search left (right = mid - 1)
   • Else: search right (left = mid + 1)

3. Return first_true_index if it's not -1, otherwise return n (insert at end)

Why This Works:

• When nums[mid] >= target, mid could be the insertion point, so we save it and search left for a possibly earlier position
• When nums[mid] < target, the insertion point must be after mid
• If first_true_index remains -1, all elements are smaller than target, so insert at the end

Time Complexity: O(log n) - we halve the search space in each iteration Space Complexity: O(1) - only using constant extra space

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)
• left = 0, right = 4, first_true_index = -1

Iteration 1:

• Calculate mid = (0 + 4) // 2 = 2
• Check nums[2] = 5 >= 4? Yes
• first_true_index = 2, right = 1

Iteration 2:

• left = 0, right = 1
• Calculate mid = (0 + 1) // 2 = 0
• Check nums[0] = 1 >= 4? No
• left = 1

Iteration 3:

• left = 1, right = 1
• Calculate mid = (1 + 1) // 2 = 1
• Check nums[1] = 3 >= 4? No
• left = 2

Termination:

• Now left = 2, right = 1, so left > right
• Loop ends
• Return first_true_index = 2

Verification: Inserting 4 at index 2 gives us [1, 3, 4, 5, 7, 9], which maintains sorted order.

Edge Case Example: Target larger than all elements

For nums = [1, 3, 5] and target = 7:

• After the search, first_true_index remains -1 (no element >= 7)
• Return n = 3 (insert at end)

Edge Case Example: Target smaller than all elements

For nums = [3, 5, 7] and target = 1:

• First iteration: nums[1] = 5 >= 1 → first_true_index = 1
• Eventually finds first_true_index = 0
• Return 0 (insert at beginning)

Time and Space Complexity

Time Complexity: O(log n), where n is the length of the array nums. The algorithm uses the binary search template with while left <= right. In each iteration, either left = mid + 1 or right = mid - 1, halving the search range. Maximum iterations: log₂(n).

Space Complexity: O(1). The algorithm uses only constant extra space for variables (left, right, mid, firstTrueIndex), regardless of input size. No recursive calls or additional data structures.

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

Common Pitfalls

1. Using Wrong Binary Search Template Variant

The Pitfall: Using while left < right with right = mid instead of the standard template with first_true_index tracking.

Example of the Issue:

# Non-standard variant
while left < right:
    mid = (left + right) // 2
    if nums[mid] >= target:
        right = mid
    else:
        left = mid + 1
return left

Solution: Use the standard binary search template with explicit answer tracking:

left, right = 0, n - 1
first_true_index = -1

while left <= right:
    mid = (left + right) // 2
    if nums[mid] >= target:
        first_true_index = mid
        right = mid - 1
    else:
        left = mid + 1

return first_true_index if first_true_index != -1 else n

2. Forgetting to Handle first_true_index = -1

The Pitfall: Not handling the case where all elements are smaller than the target.

Example Scenario:

nums = [1, 3, 5]
target = 7
# first_true_index remains -1, should return 3 (insert at end)

Solution: Always check for -1 and return n:

return first_true_index if first_true_index != -1 else n

3. Integer Overflow in Mid Calculation

The Pitfall: In languages with fixed integer sizes, (left + right) / 2 can overflow.

Solution: Use overflow-safe calculation:

mid = left + (right - left) // 2  # Safe

4. Empty Array Edge Case

The Pitfall: Not handling empty arrays properly.

Solution: The template handles this correctly: when n = 0, right = -1, the loop doesn't execute, and first_true_index = -1, so we return n = 0, which is correct.