问题：请给出一个运行时间为O(n lgn)的算法，使之能在给定一个由n个整数构成的集合S和另一个整数x时，
判断S中是否存在有两个其和等于x的元素。
题目思路：先将集合S用归并排序排好序，因为归并排序的运行时间为O(n lgn)；设置low和
high两个标志指向集合的两端，将两个点相加与x比较，如果偏小，则将low向后移，如果偏小
则将high向前移。
1 #include2 #include 3 4 void Merge(int a[], int p, int q, int r); 5 void Merge_sort(int a[], int p, int r); 6 bool judge_sum(int a[], int p, int r, int x); 7 8 int main() 9 {10 int n;11 scanf("%d",&n);12 13 int a[n + 1];14 int x;15 16 for(int i = 1; i <= n; i++){17 scanf("%d",&a[i]);18 }19 scanf("%d",&x);20 Merge_sort(a, 1, n);21 if(judge_sum(a, 1, n, x)){22 printf("exist!");23 }24 else{25 printf("not exist!");26 }27 28 return 0; 29 }30 31 bool judge_sum(int a[], int p, int r, int x){ //判断集合中是否有两个数相加等于x 32 int low = p;33 int high = r;34 35 while(low <= high){36 if(a[low] + a[high] < x)37 low++;38 else if(a[low] + a[high] > x)39 high--;40 else41 return true;42 }43 44 return false;45 }46 47 void Merge(int a[], int p, int q, int r)48 {49 int n1 = q - p + 1;50 int n2 = r - q;51 int L[n1 + 1], R[n2 + 1];52 53 for(int i = 1; i <= n1; i++){54 L[i] = a[p + i - 1];55 }56 for(int i = 1; i <= n2; i++){57 R[i] = a[q + i];58 }59 60 L[n1 + 1] = INT_MAX;61 R[n2 + 1] = INT_MAX;62 63 int i = 1, j = 1;64 for(int k = p; k <= r; k++){65 if(L[i] <= R[j]){66 a[k] = L[i];67 i++; 68 }69 else{70 a[k] = R[j];71 j++;72 }73 }74 }75 76 void Merge_sort(int a[], int p, int r)77 {78 if(p < r){79 int q = (p + r) / 2;80 Merge_sort(a, p, q);81 Merge_sort(a, q+1, r);82 Merge(a, p, q, r);83 } 84 }