算法导论2.3.7

目录

• 题目
• 题目分析
  • 证明1：x必须满足2*s[max] >= x >= 2*s[min]
• 解题过程
  • 先用并归法排序,耗费nlogn
  • 从两端向中间查找

题目

请给出一个时间复杂度为nlogn的算法，使之能够在给定一个由n个整数的构成的整合S和另一个整数x时，判断出S中是否存在有两个其和等于x的元素。

题目分析

证明1：x必须满足2*s[max] >= x >= 2*s[min]

1. 数组s[]和x均为整数。
2. 若x比数组s[]的最小值还要小，那么肯定不存在这两个数的。（这个还需要证明吗？）,进一步推理，x/2 < s[min]时，即使s[]中两个最小的数相加都会大于x。所以结果同样不存在。
3. 同理，如果s[max] < x/2，那么结果也是不存在。
4. 因此必须同时满足s[max] >= x/2 >= s[min]，因为所有的数都为整数，为了方便我们同时乘2，即2*s[max] >= x >= 2*s[min]。

这里可能有同学说了如果说可以再次缩小范围，x >= s[i] >=2*s[min]。这个我只能说，如果题目中明确了数组都是正数是没问题的。只可惜…

解题过程

先用并归法排序,耗费nlogn

从两端向中间查找

1. 首先查找s[min]+s[max],如果s[min]+s[max]>x,就缩小范围到s[min]+s[max-1],否则s[min+1]+s[max]。伪代码如下

//在排好序的基础上,假定p为s数组的最小位，r为s数组的最大位。
i=p;
j=r;
while(x!=s[i]+s[j] && i<j)
	if (x>s[i]+s[j])
		i++;
	else
		j--;
if (x==s[i]+s[j])
	printf(i,j)
esle
	printf("不存在")