习题2.3-7：设计一个算法，对于一个给定的包含n个整数的集合S和另一个给定的整数X，该算法可以在时间内确定S中是否存在两个元素，使得它们的和恰为X。

解题思路：首先应该想到的是先用一个的排序算法对S中的元素进行排序。接下来有两种处理思路，第一种思路是遍历已经排好序了的S中的所有元素a，并采用

二分查找的方法在S中查找X-a，如果能够找到，那么说明S中确实存在两个元素的和为X，算法终止。这种思路很显然是满足的限制要求的；第二种思路是我自己

想出的一个算法，这个算法也很简单，但是其正确性不是很好证明。

思路1：

思路2：

算法正确性证明：

思路1的正确性是显而易见的；思路2的正确性就不那么直观，其可能令人感到困惑的地方在于：思路2会不会漏掉某些情况？下面开始思路2的证明，

但是因为我也是初学，证明过程不是很严谨和规范。

首先，假设S中“不”包含两个和为X的元素，那么思路2的第5行的测试条件永远不会成真，那么最终算法一定会返回false。因此，证明思路2的正确性

便转化成证明：

    若S中存在两个元素a和b，使得a+b==X，那么算法一定会返回true。（*）

为了证明（*）成立，下面首先证明思路2的算法在执行过程中满足如下的特性：

    若S中存在两个元素a和b，使得a+b==X（不妨设a<=b），则在思路2的算法执行过程汇中，每一次迭代开始之前（即算法第4行执行之前），A[i…j]都包含a和b。（#）

下面采用归纳法证明（#）的成立：（令 i_k，j_k 分别表示第 k 轮迭代开始之前 i 和 j 的取值，A[i_k…j_k]表示第k轮迭代开始之前的A[i…j]）

现在（#）已经得到证明，而由（#）证（*）是很直观的。因为A[i…j]中始终包含a和b，并且每一次迭代A[i…j]的规模小一，所以，最坏的情况是迭代一直执行到i+1=j的

时候，因为此时A[i,j]包含a和b，所以A[i]一定是a，A[j]一定是b，算法检测到A[i]+A[j] = a+b=X，算法返回true。

总结：以上便是全部内容，从理论上讲思路2应该要比思路1要快（虽然它们都是）。但是很明显地，思路1的正确性更加直观。

《算法导论》2.3-7 检查集合中是否存在两数字和为指定的X--算法和证明