算法导论习题解答 2.3-7
?2.3-7 请给出一个运行为Θ(nlgn)的算法（伪码），使之能在给定一个由n个整数构成的集合S和另一个整数x时，判断出S中是否存在有两个其和等于x的元素。
解：解题思路：先对集合S进行归并排序，然后新建一个数组S1，使得S1[i] = x – S[i]，再将两个数组并起来。如果在并的过程中发现有两个元素相等且两个元素一个来自S，一个来自S1，则可以确定S中存在有两个其和等于x的元素。
Find whether x exits
1、Sort(S)
2、for i <- 0 to Length(S) – 1
3、 ??? do S1[i] <- x - S[i]
4、for i <- 0 to Length(S) – 1
5、 ??? do Merge( S,S1 )?
6、??? ??? if S[p] > S1[q]
7、??????? ??? S0[k] <- S[p]? p++ k++
8、??? ??? if S[p] < S1[q]
9、??????? ??? S0[k] <- S[q]? q++ k++
10、?????? if S[p] == S1[q]
11、????????? return true
12、return false????????
在第一行进行排序时，时间代价为Θ(nlgn)，后来的合并过程时间代价为Θ(n)，总的时间代价为Θ(nlgn)。
?
