输入一个已经按升序排序过的数组和一个数字, 在数组中查找两个数使得它们的和正好是输入的那个数字

 1 /*
 2 *题目:输入一个已经按升序排序过的数组和一个数字,
 3 *在数组中查找两个数,使得它们的和正好是输入的那个数字。
 4 *要求时间复杂度是 O(n)。如果有多对数字的和等于输入的数字,输出任意一对即可。
 5 *例如输入数组 1、2、4、7、11、15 和数字 15。由于 4+11=15,因此输出 4 和 11。
 6 */
 7 #include <utility>
 8 #include <iostream>
 9 #include <cassert>
10 using namespace std;
11 
12 pair<bool, pair<int, int> > find_pair(int *array, int len, int x)
13 {
14     assert(array);
15 
16     int *p1, *p2;
17     p1 = array, p2 = array+len-1;
18     while(p1 < p2)
19     {
20         if(*p1 + *p2 == x)
21             break;
22         else if(*p1 + *p2 < x)
23             ++p1;
24         else
25             --p2;
26     }
27     return p1 < p2 ? make_pair(true, make_pair(*p1, *p2)) : make_pair(false, make_pair(*p1, *p2));
28 }
29 int main(int argc, char const *argv[])
30 {
31     pair<bool, pair<int, int> > res;
32     int array[] = {1, 2, 4, 7, 11, 15};
33     res = find_pair(array, sizeof(array)/sizeof(int), 15);
34     if(res.first)
35         cout<<res.second.first<<" + "<<res.second.second<<" = "<<15<<endl;
36     else
37         cout<<"not found!"<<endl;
38     return 0;
39 }