给定一个有序的数组，和一个整数目标，求两个数的和等于目标的索引，索引从1开始。假设必定存在解。

有两种思路：

直接找：

vector
     
       twoSum(vector
      
       & numbers, int target) {        int s = 0, e = numbers.size() - 1;                while (true) {            if (numbers[s] + numbers[e] > target)                e--;            else if (numbers[s] + numbers[e] < target)                s++;            else {                return vector
       
         {s + 1, e + 1};            }        }    }
       
      
     

原理显而易见，最坏情况，也就O(n)，当两个索引位于中间位置。

二分查找：

vector
     
       twoSum(vector
      
       & numbers, int target) {        auto tail = upper_bound(numbers.begin(), numbers.end(), target);        auto start = numbers.begin();                for (;start != tail;) {            int other = target - *start;            ++start;            tail = lower_bound(start, tail, other);            if (other == *tail) {                vector
       
         ret = {start - numbers.begin(), tail - numbers.begin() + 1};                return move(ret);            }                        other = target - *tail;            --tail;            start = lower_bound(start, tail, other);            if (other == *start) {                vector
        
          ret = {start - numbers.begin() + 1, tail - numbers.begin() + 2};                return move(ret);            }        }    }
        
       
      
     

每次都是二分地前进后退，最坏情况下达到O(nlogn)，当两索引位于中间。

但当两个答案靠近某一端时性能较好。就leetcode结果来看，相差不大。