设a[0…n-1]是一个n个整数的已排序的数组,x是整数.请设计一个算法来确定在a[]中是否存在这样两个数,它们的和恰好是x

设a[0…n-1]是一个n个整数的已排序的数组,x是整数.请设计一个算法来确定在a[]中是否存在这样两个数,它们的和恰好是x
设a[0…n-1]是一个n个整数的已排序的数组,x是整数.请设计一个算法来确定在a[]中
是否存在这样两个数,它们的和恰好是x

设a[0…n-1]是一个n个整数的已排序的数组,x是整数.请设计一个算法来确定在a[]中是否存在这样两个数,它们的和恰好是x
假设是增序的算法如下,时间复杂度为O（n）：
#include
bool findTwoNumber(int array[],int len,int x)
{
int low = 0;
int high = len - 1;
while(low < high)
{
if ((array[low] + array[high]) > x) //如果和大于x说明当前最大数加上low之后的小数都比x大
high--;
else if ((array[low] + array[high]) < x) //如果和小于x说明当前最小数加上high之前的数都比x小
low++;
else
break;
}
if (low == high)
return false;
printf("array[%d] = %d,array[%d] = %d.",low,array[low],high,array[high]);
return true;
}
如果是减序修改循环体中的if语句修改为如下形式即可：
if ((array[low] + array[high]) < x)
high--;
else if ((array[low] + array[high]) > x)
low++;
else
break;