### Question

Given a sorted integer list and an integer, find two integer in the list such that the sum of the two integers equals the given integer. It is required that the time complexity must be O(n). For example, the sorted integer list is {1, 2, 4, 7, 11, 15} and an integer 15. The output is 4 and 11 since 4 + 11 = 15.

### Solution

Since the integer list is sorted, it is actually not that difficult. We have to create 2 pointers, 1 at the head and 1 at the tail. Check the sum of them if they equals the given integer. If not, there are 2 conditions: sum is greater or smaller than the integer. if greated, move the tail pointer backward, else move the head pointer forward.

### Example

```# foundtion to find the integers
def find_two_suitable_int(list, wanted_sum):

# check error
if len(list) <= 1:
print "list too short to work on"
return (None, None)

# pointers
tail = len(list) - 1

# find the integers
if sum == wanted_sum:
elif sum > wanted_sum:
tail = tail - 1
else:

# shows that no integers are found
print "can't find suitable integers"
return (None, None)

# main testing, output should be 11 and 4
list = [1, 2, 4, 7, 11, 15]
(x, y) = find_two_suitable_int(list, 15)
if x: print "the two integers are %s and %s" % (x, y)```
```#include <iostream.h>

bool FindTwoNumbersWithSum
(
int data[],           // 已经排序的 数组
unsigned int length,  // 数组长度
int sum,              //用户输入的 sum
int& num1,            // 输出符合和等于sum的第一个数
int& num2             // 第二个数
)
{
bool found = false;
if(length < 1)
return found;

int begin = 0;
int end = length - 1;

while(end > begin)
{
long curSum = data[begin] + data[end];

if(curSum == sum)
{
num1 = data[begin];
num2 = data[end];
found = true;
break;
}
else if(curSum > sum)
end--;
else
begin++;
}
return found;
}

int main()
{
int x,y;
int a[6]={1,2,4,7,11,15};
if(FindTwoNumbersWithSum(a,6,15,x,y) )
{
cout<<x<<endl<<y<<endl;
}
return 0;
}```

### Extended Question

1.题目假定是，只要找出俩个数，的和等于给定的数，

4,5,7,10,12

2.第14题，还有一种思路，如下俩个数组：
1、 2、  4、7、11、15     //用15减一下为
14、13、11、8、4、 0      //如果下面出现了和上面一样的数，稍加判断，就能找出这俩个数来了。