使用二分查找解决“两数之和”问题（有序数组）

题目：两数之和
描述：给定一个升序排列的整数数组numbers，从数组中找出两个数满足相加之和等于目标数target。
注意：假设每个输入只对应唯一的答案，而且不可以重复使用相同的元素，返回两数的下标值，以数组形式返回。
前面我们分别用单个for循环和双重for循环解决了两数之和问题。如果给定的数组是有序的，那么我们还可以用二分法来解决这个问题。方法的时间复杂度：单个for循环 < 二分法 < 双重for循环。虽然对于时间复杂度，二分法不是三种方式中的最优解，但是它没有引入别的数据结构（比如Map）占用更多空间，所以它的空间复杂度是很低的。
思路：x+y=target, 先固定一个值x(从下标0开始)，再用二分查找查另外一个值，找不到则固定值向右移动，继续二分查找。
时间复杂度：O(N * logN)
空间复杂度：O(1)

二分查找：
查找过程：将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。
适用场景：二分法查找适用于数据量较大时，但是数据需要先排好顺序。
算法要求：
1、必须采用顺序存储结构。
2、必须按关键字大小有序排列。

package od;

import java.util.Arrays;

/**
 * 两数之和（二分查找）
 * 给定一个升序排列的整数数组numbers，从数组中找出两个数满足相加之和等于目标数target。
 * 假设每个输入只对应唯一的答案，而且不可以重复使用相同的元素。
 * 返回两数的下标值，以数组形式返回。
 * 原文地址：https://www.codernav.com/2828.html
 * 更多算法详解：https://www.codernav.com
 */
public class OdTest24 {
    public static void main(String[] args) {
        int[] result = f(new int[]{1, 2, 3, 4, 5, 6}, 10);
        System.out.println(Arrays.toString(result));
    }

    private static int[] f(int[] nums, int target) {
        // 遍历数组, x+y=target, 每次循环中nums[i]相当于x, y=target-x
        for (int i = 0; i < nums.length; i++) {
            // 使用二分法查找y
            int left = i;
            int right = nums.length - 1;
            // 循环结束条件，左右标记重合
            while (left <= right) {
                // 中间元素的下标
                int mid = left + (right - left) / 2;
                if (nums[mid] == target - nums[i]) { // 中间元素就是要找的y
                    return new int[]{i, mid};
                } else if (nums[mid] > target - nums[i]) { // y在mid的左侧, right左移
                    right = mid - 1;
                } else { // y在mid的右侧，left右移
                    left = mid + 1;
                }
            }
        }

        return new int[0];
    }
}