Solution Approach

The solution implements a binary search strategy to find the two numbers that sum to the target. We use the standard binary search template with first_true_index to find the complement.

Algorithm Overview: The approach iterates through each element in the array and uses binary search to find its complement.

Binary Search Template: For each element numbers[i], we search for complement = target - numbers[i] using the template:

left, right = i + 1, n - 1
first_true_index = -1

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

Step-by-Step Implementation:

1. Iterate through the array: We loop through indices from 0 to n-2 (where n is the length of the array). We don't need to check the last element because it would have no elements after it to pair with.

2. Calculate the complement: For each numbers[i], we calculate the required complement:

   complement = target - numbers[i]

3. Binary search with template: We use the boundary-finding template:

   • Initialize left = i + 1, right = n - 1, and first_true_index = -1
   • The feasible condition is numbers[mid] >= complement
   • When feasible, save first_true_index = mid and search left with right = mid - 1
   • When not feasible, search right with left = mid + 1

4. Check if complement exists: After binary search:

   if first_true_index != -1 and numbers[first_true_index] == complement:

   • first_true_index != -1: Ensures we found a valid position
   • numbers[first_true_index] == complement: Confirms the value equals complement (not just >= complement)

5. Return the result: Return 1-indexed positions [i + 1, first_true_index + 1]

Time Complexity: O(n log n) - We iterate through n elements, performing O(log n) binary search each. Space Complexity: O(1) - Only constant extra space used.

Example Walkthrough

Let's walk through a concrete example to understand how the binary search template works.

Example: numbers = [1, 3, 4, 7, 11], target = 10

We need to find two numbers that sum to 10. The answer should be [2, 4] because numbers[2] + numbers[4] = 3 + 7 = 10 (using 1-based indexing).

Step-by-step execution:

Iteration 1: i = 0 (examining numbers[0] = 1)

• Calculate complement: complement = 10 - 1 = 9
• Binary search for first index where numbers[mid] >= 9 in range [1, 4]:
  • left = 1, right = 4, first_true_index = -1
  • mid = 2: numbers[2] = 4 < 9 → left = 3
  • mid = 3: numbers[3] = 7 < 9 → left = 4
  • mid = 4: numbers[4] = 11 >= 9 → first_true_index = 4, right = 3
  • left > right, exit loop
• Check: first_true_index = 4, but numbers[4] = 11 ≠ 9
• No match found, continue

Iteration 2: i = 1 (examining numbers[1] = 3)

• Calculate complement: complement = 10 - 3 = 7
• Binary search for first index where numbers[mid] >= 7 in range [2, 4]:
  • left = 2, right = 4, first_true_index = -1
  • mid = 3: numbers[3] = 7 >= 7 → first_true_index = 3, right = 2
  • mid = 2: numbers[2] = 4 < 7 → left = 3
  • left > right, exit loop
• Check: first_true_index = 3, and numbers[3] = 7 == 7 ✓
• Match found! Return [i + 1, first_true_index + 1] = [2, 4]

Visual representation of Iteration 2:

Array:     [1, 3, 4, 7, 11]
Indices:    0  1  2  3  4
            ↑
         i = 1
         numbers[i] = 3

Search for first index where value >= 7 in range [2, 4]
Template finds first_true_index = 3 (where numbers[3] = 7)
Verify: numbers[3] == complement (7 == 7) ✓
Return [1+1, 3+1] = [2, 4] (converting to 1-based indexing)

The algorithm successfully finds that elements at 1-based positions 2 and 4 (values 3 and 7) sum to our target of 10.

Time and Space Complexity

The time complexity is O(n × log n), where n is the length of the array numbers. This is because:

• The outer loop runs n - 1 times, iterating through each element as a potential first number
• For each iteration, bisect_left performs a binary search on the remaining portion of the array (from index i + 1 to the end), which takes O(log n) time
• Therefore, the overall time complexity is O(n) × O(log n) = O(n × log n)

The space complexity is O(1). The algorithm only uses a constant amount of extra space for variables i, j, x, and n, regardless of the input size. The bisect_left function performs binary search iteratively without using additional space proportional to the input.

Common Pitfalls

1. Using the Wrong Binary Search Template Variant

A common mistake is using while left < right with right = mid instead of the correct template.

Incorrect approach:

# WRONG: Using incorrect template
while left < right:
    mid = (left + right) // 2
    if numbers[mid] >= complement:
        right = mid
    else:
        left = mid + 1
return left  # Returns insertion point, not necessarily the answer

Solution: Use the correct template with first_true_index:

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

2. Using the Same Element Twice

Accidentally allowing the same array element to be used twice in the sum.

Why it fails: If target = 4 and numbers = [1, 2, 3], when i = 1 (value 2), the complement is also 2. Without restricting the search range, binary search might return index 1 again.

Solution: Always initialize left = i + 1 to search only in the remaining array.

3. Forgetting to Convert to 1-Based Indexing

The problem explicitly requires 1-indexed results, but the array uses 0-based indexing.

Solution: Always add 1 to both indices:

return [i + 1, first_true_index + 1]

4. Not Checking if first_true_index Contains the Exact Complement

The binary search finds the first position where numbers[mid] >= complement, but this doesn't guarantee equality.

Incorrect approach:

# WRONG: Assumes first_true_index always has the complement
return [i + 1, first_true_index + 1]

Solution: Always verify both that first_true_index != -1 and numbers[first_true_index] == complement:

if first_true_index != -1 and numbers[first_true_index] == complement:
    return [i + 1, first_true_index + 1]