CLRS 2.3-7 ：请给出一个运行时间为O(nlgn)的算法，是之能在一个由n个整数构成的集合S和另一个整数x时，判断出S中是否存在有两个其和等于x的元素。
算法思想：
1.先运用合并排序进行排序 O(nlgn)，
2.然后运用二分查找法寻找y，y = x - a[i]；
代码如下：
1 #include <iostream>
2 using namespace std;
3
4 void sort(int*&a, int p, int q, int r)
5 {
6 int* left =new int[q - p +1];
7 int* right =new int[r - q];
8 for(int i =0; i < q - p +1; i++)
9 left[i] = a[p + i];
10 for(int i =0; i < r - q; i++)
11 right[i] = a[q + i +1];
12
13 int m =0;
14 int n =0;
15 //书上在这里用的是在数组末尾添加一个数，即"哨兵牌"
16 //作者同时让我们不用"哨兵牌"来实现
17 //我在这里采取的是，如果到达一个数组的末尾，
18 //那么另外一个数组的剩余元素就不用比较了，然后可以完全复制到a，见27行.
19 //时间复杂度未变，因为27行的循环紧跟20行的循环而已，你可以看到结束条件都是i<=r,j<=r，然后break
20 for(int i = p; i <= r; i++) {
21 if(left[m] <= right[n]) {
22 a[i] = left[m];
23 if(m++== q-p) {
24 for(int j = i +1; j <= r; j++)
25 a[j] = right[n++];
26 break;
27 }
28 } else {
29 a[i] = right[n];
30 if(n++== r-q-1) {
31 for(int j = i +1; j <= r; j++)
32 a[j] = left[m++];
33 break;
34 }
35 }
36 }
37
38 delete[] left;
39 delete[] right;
40 }
41 void merge(int*&a, int m, int n)
42 {
43 if(m < n) {
44 int q = (m + n)/2;
45 merge(a, m, q);
46 merge(a, q+1, n);
47 sort(a, m, q, n);
48 }
49 }
50
51 //二分查找
52 bool binary_search(int* a, int n, int goal)
53 {
54 int middle = (n -1)/2;
55 int high = n -1;
56 int low =0;
57 while(low <= high) {
58 if(a[middle] == goal)
59 return true;
60 else if(a[middle] >= goal)
61 high = middle -1;
62 else
63 low = middle +1;
64 middle = (low + high)/2;
65 }
66 return false;
67 }
68
69 int main()
70 {
71 const int LEN =1000000;
72 //用max来代表最大数，你可以任意选取
73 int max =100000000;
74 int* a =new int[LEN];
75 for(int i =0; i < LEN; i++)
76 a[i] = LEN - i;
77 merge(a, 0, LEN -1);
78
79 int x;
80 cin>>x;
81 if(!(x%2)) {
82 for(int i =0; i < LEN; i++)
83 if(a[i] == x/2) {
84 a[i] = max;
85 break;
86 }
87 }
88
89 for(int i =0; i < LEN; i++)
90 if(binary_search(a, LEN, x - a[i])) {
91 cout<<"YES"<<endl;
92 break;
93 }
94
95 delete a;
96 return 0;
97 }