数据结构——算法之（005）（输入一个已经按升序排序过的数组跟一个数字， 在数组中查找两个数，使得它们的和正好是输入的那个数字）

数据结构——算法之（005）（输入一个已经按升序排序过的数组和一个数字， 在数组中查找两个数，使得它们的和正好是输入的那个数字）

【申明：本文仅限于自我归纳总结和相互交流，有纰漏还望各位指出。 联系邮箱：Mr_chenping@163.com】

题目：输入一个已经按升序排序过的数组和一个数字，
在数组中查找两个数，使得它们的和正好是输入的那个数字。
要求时间复杂度是O(n)。如果有多对数字的和等于输入的数字，输出任意一对即可。
例如输入数组1、2、4、7、11、15和数字15。由于4+11=15，因此输出4和11。

题目分析：

一、既然是排序过了，且是升序，那么最大值在最右边，最小值在左边

二、通过2个指针start、end分别指向数组的头和尾，当start+end大于和时end--，否则start--

算法实现：

#include <stdio.h>

void get_sum_num(int *array, int size, int sum)
{
	int *begin = &array[0];
	int *end = &array[size-1];

	while(begin < end)
	{
		if(*begin + *end > sum)
		{
			end--;
		}
		else if(*begin + *end < sum)
		{
			begin++;
		}
		else
		{
			break;
		}
	}
	printf("[%d] = %d + %d\n", sum, *begin, *end);
}

int main()
{
	int array[]={1, 2, 3, 5, 8, 13};
	get_sum_num(array, 6, 5);	

	return 0;
}