Two Sum II - Input Array Is Sorted

Given a sorted array of integers, find two numbers such that they add up to a specific target value. This problem is a variation of the classic Two Sum problem, but leverages the fact that the input array is sorted to optimize the solution. Efficiently finding pairs that sum to a target is a fundamental problem with applications in areas like financial analysis and data processing.

Problem Description

You are given a sorted array of integers numbers and an integer target. Your task is to find two distinct indices i and j in the array such that numbers[i] + numbers[j] == target. The indices i and j must be different.

What needs to be achieved:

• Identify two numbers within the sorted array that sum to the target value.
• Return the indices of these two numbers.
• If no such pair exists, return an empty array or null (depending on the language's conventions for indicating no result).

Key Requirements:

• The input array numbers is guaranteed to be sorted in ascending order.
• The indices i and j must be distinct (i.e., i != j).
• The solution should be efficient, taking advantage of the sorted nature of the input.

Expected Behavior:

The function should return an array containing the two indices [i, j] where numbers[i] + numbers[j] == target. The order of the indices in the returned array does not matter.

Edge Cases to Consider:

• Empty input array: Should return an empty array or null.
• Array with only one element: Should return an empty array or null.
• Target value is less than the smallest element or greater than the largest element in the array: Should return an empty array or null.
• Duplicate numbers in the array: The problem statement requires distinct indices, so handle duplicates appropriately.

Examples

Example 1:

Input: numbers = [2,7,11,15], target = 9
Output: [0, 1]
Explanation: 2 + 7 = 9, where 2 is at index 0 and 7 is at index 1.

Example 2:

Input: numbers = [2,3,4], target = 6
Output: [0, 2]
Explanation: 2 + 4 = 6, where 2 is at index 0 and 4 is at index 2.

Example 3:

Input: numbers = [-1,0], target = -1
Output: [0, 1]
Explanation: -1 + 0 = -1, where -1 is at index 0 and 0 is at index 1.

Example 4: (Edge Case - No Solution)

Input: numbers = [2,7,11,15], target = 10
Output: []
Explanation: No two numbers in the array sum to 10.

Constraints

• 1 <= numbers.length <= 10^4
• -10^9 <= numbers[i] <= 10^9
• -10^9 <= target <= 10^9
• The array numbers is sorted in ascending order.
• Performance: The solution should ideally have a time complexity of O(n) or better, leveraging the sorted input.

Notes

Consider using a two-pointer approach to efficiently search for the pair. Since the array is sorted, you can start with one pointer at the beginning and one at the end, and adjust their positions based on the sum compared to the target. Think about how the sorted property allows you to eliminate possibilities quickly.