[LeetCode 167. Two Sum II - Input Array is sorted][https://leetcode-cn.com/problems/two-sum-ii-input-array-is-sorted/solution/er-fen-shuang-zhi-zhen-liang-chong-jie-f-eg5d/]
首先，$nums.length <= 3 * 10^4$，则$O(n^2)$的解法也大致能通过，最简单的两个for 循环遍历，直到找到为止（因为题目说明了唯一。找到即为正确解），暴力法必定能解决。
但是，我们继续往下想，之前的解法并没有利用数组有序性，因此必然能优化。有序数组你会想到什么呢？又是查找，很显然二分查找，而且二分查找的复杂度只有$O(logn)$。但是二分查找是查找某个元素是否在有序数组中，这里需要在numbers升序数组中找到和为target的两个数。想到了吗？利用和这一限制，固定一个数，然后二分搜索另一个数即可，然后对第一个固定的数遍历即可。这样子就可以找到唯一解。
为什么呢？我们简单说明，第一个数$a$从头找到尾，然后对$target-a$用二分查找，实际上等价于我们之前想的暴力搜索所有可能，只是利用有序和二分查找跳过了一些必然不可能的情况而已，所以相当于其实还是全部搜索了一遍。
### 代码
class Solution {
public int[] twoSum(int[] numbers, int target) {
int len = numbers.length;
int index1 = 0 , index2 = 0;
for ( ; index1 < len-1; index1++) {
index2 = binarySearch(numbers, target-numbers[index1], index1+1, len-1);
if (index2 != -1)
break;
}
// 健壮性：对不存在的情况加个特判
return new int[] {index1+1, index2+1};
}
public static int binarySearch(int[] nums, int target, int left, int right) {
int low = left, high = right;
while (low <= high) {
int mid = low + (high - low)/2;
if (nums[mid] == target)
return mid;
if (nums[mid] < target)
low = mid + 1;
else
high = mid - 1;
}
return -1;
}
}复杂度分析
时间复杂度: O(nlogn)，因为一个for循环遍历索引[0, numbers.length - 2]，然后固定index1后，二分查找剩余的部分[index1+1, numbers.length-1]，最坏O(logn)
空间复杂度: O(1)
【注】二分查找为什么不需要搜索整个numbers数组呢？
1. 避免使用同一个数两次的情况
2. 保证index1 < index2
3. 正确性：假设当前index1 = k, 则index1 = k-1时，已经判断过index1 = k-1和index2 = k的情况，因此反过来，当index1=k时，index2无需去搜索k-1，同理，当index1=k时，无需去搜索index2 <= k的所有情况，之前的index1都搜索过了。
再考虑还有没有优化的可能呢？题目中给的有序性是否用到极致了呢？解法一是否也可以看做两个指针呢，其中index2利用升序，可以用二分来优化搜索过程，那么为什么index1不能利用升序性呢？
后面我就想到了可以设置两个指针，让它们分别来动，怎么判断谁该动？它们的初始值应该放在哪？终止条件呢（这个容易，当双指针指向的数字之和等于target即可终止），怎么保证一定搜索到所有的情况呢？
下面来说一下我的考虑：
1. 其实第一个和第二问题我是同时想到的，将左右指针分别置成数组的两端，left = 0, right = numbers.length-1。计算当前的和**sum = numbers[left] + numbers[right]**，如果当前和小于target，那么说明需要继续增加，则left++；如果大于target， 那么right--；
2. 否则相等，直接返回（终止条件给出）
3. 说明理由：对于给定升序数组，任意两个数的和是在区间[numbers[left]+numbers[left+1], numbers[right-1]+numbers[right]]之间，且该和可看成是一个递增的函数，而我们取的初始值正好将和区间分为了两部分，如果我们发现大于，则将闭区间向和更小的一侧靠近即缩小闭区间右端点；如果小于，则扩大。我们这样必然能搜索必能搜索到所有的取值，又因为该值时唯一的，因此必定成立。
其实这个思想类似于二分，只是这个时候不是根据区间中点的值来缩小或放大，而是根据两个区间端点的和来缩放，并且恰好由于升序性，区间端点的和与区间端点之间存在单调递增的关系。
### 代码
class Solution {
public int[] twoSum(int[] numbers, int target) {
int left = 0, right = numbers.length - 1;
while (left < right) {
int sum = numbers[left] + numbers[right];
if (sum == target)
return new int[] {left+1, right+1};
if (sum < target)
left++;
else // sum > target
right--;
}
return new int[] {-1, -1};
}
}复杂度分析
时间复杂度: O(n),最坏情况某个指针遍历整个数组
空间复杂度: O(1)
【注】为什么循环条件要设成left < right呢？
因为，这表示一个闭区间，且必须同一个数不能用两次，所以不能取等于；
而当right指针反过来越过left指针，实际上等同于right指针和left指针交换了，还是去搜之前已经搜过的情况了，没必要。
解法一运行时间3ms， 超过了37%
解法二运行时间1ms, 超过92.76%