453. Two Sum in Sorted Array (Binary Search Variant)

Given a 1-indexed sorted array numbers and an integer target, find two numbers that add up to target. Return their 1-indexed positions [index1, index2] with index1 < index2. Guaranteed exactly one solution exists or return [-1,-1] if none.

Input: A sorted integer array numbers and integer target.

Output: [index1, index2] (1-indexed), or [-1,-1] if not found.

Examples

Input: [2,7,11,15], 9
Output: [1,2]
Explanation: numbers[1]+numbers[2]=2+7=9. Return 1-indexed [1,2].

Input: [-1,0,1,2], 1
Output: [2,3]
Explanation: numbers[2]+numbers[3]=0+1=1. Return [2,3].

Input: [2,7,11,15], 100
Output: [-1,-1]
Explanation: No pair sums to 100.

Constraints

• 2 <= numbers.length <= 3*10^4
• -1000 <= numbers[i] <= 1000
• Sorted non-decreasing

Asked by