/**
1. 二分: 因为数组已经排好序了, 所以可以二分找到答案;  需要特判下, 如果结果与当前下标相等, 抛弃这次查找 O(nlogn)
2. 双指针: 数组严格递增. 把双指针分别指向数组两端, 因为和为target, 所以i向右移动时, j需要向右移动 并且 i < j, O(n)
*/

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        // return divide(numbers, target);
        return doublePoint(numbers, target);
    }

    public int[] doublePoint(int[] numbers, int target){
        for (int i = 0, j = numbers.length - 1; i < j; i ++ ){
            while (j > i + 1 && numbers[i] + numbers[j-1] >= target) j--;
            if (numbers[i] + numbers[j] == target){
                int[] res = {i + 1, j + 1};
                return res;
            }
        }   
        return null;
    }

    public int[] divide(int[] numbers, int target){
        for (int i = 0 ; i < (numbers.length >> 1) + 1; i ++){
            int j = lowerBound(numbers, target - numbers[i]);
            if (numbers[i] + numbers[j] == target && i != j){
                int[] res = {Math.min(i, j) + 1, Math.max(i, j) + 1};
                return res;
            }
        }
        return null;
    }

    public int lowerBound(int[] nums, int target){
        int l = 0, r = nums.length - 1;
        while (l < r){
            int mid = (l + r) >> 1;
            if (nums[mid] >= target) r = mid;
            else l = mid + 1;
        }
        return l;
    }
}