Problem Description

You are given a 1-indexed array of integers called numbers that is already sorted in non-decreasing order (smallest to largest). Your task is to find two numbers in this array that add up to a specific target value.

The key requirements are:

1. The array uses 1-based indexing (the first element is at index 1, not 0)
2. You need to find exactly two different elements whose sum equals the target
3. Return the indices of these two numbers as [index1, index2] where index1 < index2
4. Since the array is 1-indexed, you need to add 1 to the actual array positions
5. You cannot use the same element twice (the two numbers must be at different positions)
6. The problem guarantees exactly one solution exists
7. Your solution must use only constant extra space (O(1) space complexity)

For example, if numbers = [2, 7, 11, 15] and target = 9, you would return [1, 2] because numbers[1] + numbers[2] = 2 + 7 = 9.

The solution leverages the sorted nature of the array. For each element numbers[i], it uses binary search to look for the complement value target - numbers[i] in the remaining portion of the array (from position i+1 onwards). The bisect_left function efficiently finds where the complement would be positioned in the sorted array. If the complement exists at that position, the function returns the 1-indexed positions of both numbers.

Intuition

When we need to find two numbers that sum to a target, the most straightforward approach would be to check every possible pair, but that would take O(n²) time. However, we can take advantage of the fact that the array is already sorted.

The key insight is that for any number in our array, we know exactly what its complement needs to be: complement = target - current_number. Since the array is sorted, we can efficiently search for this complement using binary search instead of checking every element.

Here's the thought process:

1. Pick a number from the array (let's call it numbers[i])
2. Calculate what value we need to find: x = target - numbers[i]
3. Since the array is sorted, we can use binary search to quickly check if x exists in the remaining part of the array

Why search only in the remaining part (from i+1 onwards)? Because:

• We can't use the same element twice
• If the complement existed before position i, we would have already found it when we processed earlier elements
• This prevents us from finding duplicate pairs like [i, j] and [j, i]

Binary search reduces the search time from O(n) to O(log n) for each element we check. Since we might need to check up to n elements in the worst case, the overall time complexity becomes O(n log n), which is much better than the brute force O(n²) approach.

The bisect_left function finds the leftmost position where x would fit in the sorted array. If the element at that position equals x, we've found our pair. If not, x doesn't exist in the array, and we move on to the next element.

Solution Approach

The solution implements a binary search strategy to find the two numbers that sum to the target. Let's walk through the implementation step by step:

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

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:

   x = target - numbers[i]

   This x is the value we need to find in the remaining array to achieve our target sum.

3. Binary search for the complement: We use Python's bisect_left function to perform binary search:

   j = bisect_left(numbers, x, lo=i + 1)

   • bisect_left returns the leftmost insertion position for x in the sorted array
   • The lo=i + 1 parameter ensures we only search in the portion of the array after index i
   • This prevents using the same element twice and avoids duplicate pairs

4. Check if complement exists: After getting the position j, we verify two conditions:

   if j < n and numbers[j] == x:

   • j < n: Ensures the position is within array bounds
   • numbers[j] == x: Confirms that the element at position j is actually our target complement

5. Return the result: If we find a valid pair, we return their 1-indexed positions:

   return [i + 1, j + 1]

   We add 1 to both indices because the problem uses 1-based indexing.

Time Complexity: O(n log n)

• We iterate through at most n elements
• For each element, we perform a binary search which takes O(log n)

Space Complexity: O(1)

• We only use a constant amount of extra space for variables i, j, and x
• This satisfies the problem's requirement of using only constant extra space

The beauty of this solution lies in leveraging the sorted nature of the array to transform what could be an O(n²) brute force approach into an efficient O(n log n) solution using binary search.

Example Walkthrough

Let's walk through a concrete example to understand how the binary search solution 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: x = 10 - 1 = 9
• Binary search for 9 in [3, 4, 7, 11] (from index 1 onwards)
• bisect_left returns position 4 (where 9 would be inserted)
• Check: numbers[4] = 11 ≠ 9
• No match found, continue

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

• Calculate complement: x = 10 - 3 = 7
• Binary search for 7 in [4, 7, 11] (from index 2 onwards)
• bisect_left returns position 3 (where 7 is located)
• Check: numbers[3] = 7 = 7 ✓
• Match found! Return [i + 1, j + 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 x = 7 in subarray [4, 7, 11] (indices 2, 3, 4)
Binary search finds 7 at index 3
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. The binary search makes this process efficient by quickly locating the complement value rather than checking every remaining element.

Solution Implementation

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 Same Element Twice

One of the most common mistakes is accidentally allowing the same array element to be used twice in the sum. This can happen if you don't properly restrict the search range.

Incorrect approach:

# WRONG: This might find the same element twice
j = bisect_left(numbers, complement)  # Searches entire array
if j < n and numbers[j] == complement:
    return [i + 1, j + 1]

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, giving us the same element twice.

Solution: Always search starting from i + 1:

j = bisect_left(numbers, complement, lo=i + 1)  # Correct

2. Forgetting to Convert to 1-Based Indexing

The problem explicitly requires 1-indexed results, but Python uses 0-based indexing. Forgetting to add 1 to the indices is a frequent error.

Incorrect approach:

# WRONG: Returns 0-based indices
return [i, j]

Solution: Always add 1 to both indices:

return [i + 1, j + 1]  # Correct 1-based indexing

3. Not Checking if the Found Position Contains the Target Value

bisect_left returns where the value should be inserted, not necessarily where it exists. Failing to verify the actual value can lead to incorrect results.

Incorrect approach:

# WRONG: Assumes the complement exists without verification
j = bisect_left(numbers, complement, lo=i + 1)
return [i + 1, j + 1]  # Might return wrong indices

Why it fails: If the complement doesn't exist, bisect_left still returns a valid insertion position, but numbers[j] won't equal the complement.

Solution: Always verify both bounds and value:

if j < n and numbers[j] == complement:  # Correct validation
    return [i + 1, j + 1]

4. Using Two Pointers Incorrectly with Additional Constraints

While the two-pointer approach is valid for this problem, mixing it with binary search or implementing it incorrectly can cause issues.

Alternative correct two-pointer approach:

def twoSum(self, numbers: List[int], target: int) -> List[int]:
    left, right = 0, len(numbers) - 1
  
    while left < right:
        current_sum = numbers[left] + numbers[right]
        if current_sum == target:
            return [left + 1, right + 1]
        elif current_sum < target:
            left += 1
        else:
            right -= 1

This approach is actually more efficient (O(n) time) than the binary search method, but both are valid solutions.