算法导论习题2.3-7

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

解答：

首先对S进行排序，使用合并算法进行排序，排序算法的时间复杂度为nlogn。

然后对排序的S从左到右（即从大到小）进行算法，首先锁定一个数i，这个数小于x的一半，然后从这个数的右边开始查找x-i，使用2分法查找，算法的时间复杂度小于nlogn,所以总的时间复杂度还是nlogn。

1. #include<iostream>
3. constintMAXINT=0xFFFF-1;
5. voidMerge(intA[],intstart,intmid,intend)
6. {
7. intlen1=mid-start+1+1;//加一个位置用于保存哨兵
8. intlen2=end-mid+1;//加一个位置用于保存哨兵
9. int*L=newint[len1];
10. int*R=newint[len2];
11. for(inti=0;i<len1-1;i++)
12. L[i]=A[start+i];
13. L[len1-1]=MAXINT;
14. for(intj=0;j<len2-1;j++)
15. R[j]=A[mid+j+1];
16. R[len2-1]=MAXINT;
17. i=0;j=0;
18. for(intk=start;k<=end;k++)
19. {
20. if(L[i]<=R[j])
21. {
22. A[k]=L[i];
23. i++;
24. }
25. else
26. {
27. A[k]=R[j];
28. j++;
29. }
30. }
31. }
32. voidMergeSort(intA[],intstart,intend)
33. {
34. if(start<end)
35. {
36. intmid=(end+start)/2;
37. MergeSort(A,start,mid);
38. MergeSort(A,mid+1,end);
39. Merge(A,start,mid,end);
40. }
41. }
42. voidFind(intA[],intn,intx)
43. {
44. intneedValue;
45. intleft,right,leftPosition,middle;
46. leftPosition=0;
47. intcount=0;
48. while(A[leftPosition]<=x/2)
49. {
50. needValue=x-A[leftPosition];
51. left=leftPosition+1;
52. right=n-1;
53. while(left<=right)
54. {
55. middle=(left+right)/2;
56. if(A[middle]>needValue)
57. right=middle-1;
58. else
59. if(A[middle]<needValue)
60. left=middle+1;
61. else
62. {
63. std::cout<<"the"<<++count<<":";
64. std::cout<<x<<"="<<A[leftPosition]<<"+"<<needValue<<std::endl;
65. inttemp;
66. temp=middle;
67. while(A[--temp]==needValue)
68. {
69. std::cout<<"the"<<++count<<":";
70. std::cout<<x<<"="<<A[leftPosition]<<"+"<<needValue<<std::endl;
71. }
72. temp=middle;
73. while(A[++temp]==needValue)
74. {
75. std::cout<<"the"<<count++<<":";
76. std::cout<<x<<"="<<A[leftPosition]<<"+"<<needValue<<std::endl;
77. }
78. break;
79. }
80. }
81. leftPosition++;
82. }
83. std::cout<<"thetotalnumberis"<<count<<std::endl;
84. }
86. intmain(void)
87. {
88. int*a;
89. intx;
90. intn;
91. std::cout<<"Pleaseinputthetwonumber'ssum:"<<std::endl;
92. std::cin>>x;
93. std::cout<<"Pleaseinputthearray'ssize:/n";
94. std::cin>>n;
95. a=newint[n];
96. std::cout<<"Pleaseinputthearray'value:"<<std::endl;
97. for(inti=0;i<n;i++)
98. std::cin>>a[i];
99. MergeSort(a,0,n-1);
100. std::cout<<"Thesortednumberseries:";
101. for(i=0;i<n;i++)
102. std::cout<<""<<a[i];
103. std::cout<<std::endl<<"theresult:/n";
104. Find(a,n,x);
105. return0;
106. }