Given an array of integers that is already sorted in ascending order, find two numbers such that they add up to a specific target number.
The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.
You may assume that each input would have exactly one solution and you may not use the same element twice.

Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2

Solution1：Two pointers

思路： 因为是已经排好序的，所以双指针前后找，根据指向元素和 和 target相对大小 来调整指针位置
Time Complexity: O(N) Space Complexity: O(1)

Solution2：Binary Search

思路： 对每个元素都去binary search(since sorted)查找它需要的另一个元素(their sum == target)
Time Complexity: O(N logN) Space Complexity: O(1)

Solution3：Binary Search [Template]

思路：
Time Complexity: O(N logN) Space Complexity: O(1)

Solution1 Code：

class Solution1 {
    public int[] twoSum(int[] numbers, int target) {
        int[] ret = new int[2];
        if(numbers == null || number.length < 2) return ret;
        
        int start = 0, end = numbers.length - 1;
        while(start < end) {
            if(numbers[start] + numbers[end] == target) {
                ret[0] = start + 1;
                ret[1] = end + 1;
                return ret;
            }
            if(numbers[start] + numbers[end] > target) {
                end--;
            }
            else {
                start++;
            }
        }
        return ret;
    }
}

Solution2 Code：

class Solution2 {
    public int[] twoSum(int[] numbers, int target) {
        int ret[] = new int[2];
        if(numbers == null) return ret;
        
        for(int i = 0; i < numbers.length; i++) {
            // for every element, binary search the counterpart that sums to target
            int start = i + 1, end = numbers.length - 1;
            int gap = target - numbers[i];
            while(start <= end) {
                int mid = start + (end - start) / 2;
                if(numbers[mid] == gap) { // found
                    ret[0] = i + 1;
                    ret[1] = mid + 1;
                    return ret;
                }
                else if(numbers[mid] > gap) end = mid - 1;
                else start = mid + 1;
            }
        }
        // not found
        return ret;
    }
}

Solution3 [Binary Search Template] Code：

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int[] ret = new int[]{-1, -1};
        if(numbers == null || numbers.length < 2) return ret;
        
        for(int i = 0; i < numbers.length - 1; i++) {
            int tg = target - numbers[i];
            int left = i + 1, right = numbers.length - 1;
            while(left + 1 < right) {
                int mid = left + (right - left) / 2;
                if(numbers[mid] == tg) {
                    ret[0] = i + 1;
                    ret[1] = mid + 1;
                    return ret;
                }
                else if(numbers[mid] < tg) {
                    left = mid;
                }
                else {
                    right = mid;
                }
            }
            if(numbers[left] == tg) {
                ret[0] = i + 1;
                ret[1] = left + 1;
                return ret;
            }
            else if(numbers[right] == tg) {
                ret[0] = i + 1;
                ret[1] = right + 1;
                return ret;
            }
        }
        
        return ret;
    }
}