题目：（见于《算法导论》原书第二版P23,2.3-7
请给出一个运行时间为O(nlgn)的算法，使之能在给定的一个由n个整数构成的集合S和另一个整数x时，判断出S中是否存在两个其和等于x的元素。
分析：
题目明确给出要求运行时间为O(nlgn)，这样的话，首先想到的枚举算法行不通，因为在不存两数之和为x的时候，其时间复杂度为O(n^2)。
再考虑另外的算法，对于这个问题，不妨首先对数组进行排列，而排列可以做到运行时间为O(nlgn)的时间界，排序好，然后再来个二分搜索，二分搜索的时间复杂度也是O(nlgn)，这样看来，总的看来，时间的复杂度可以满足题目要求。
具体的代码如下：
1 #include<iostream> 2 #include<algorithm> 3 using namespace std; 4 5 bool isexnum(int *a, int n,int x) 6 { 7 sort(a,a+10);//先做排序 8 for(int i=0; i<n; i++) 9 { 10 if(binary_search(a,a+i,x-a[i])||binary_search(a+i+1,a+n,x-a[i]))//进行二分搜索 11 { 12 return true; 13 break; 14 } 15 } 16 return false; 17 } 18 19 int main() 20 { 21 int a[10]={2,1,8,6,3,4,3,9,0,7}; 22 23 if(isexnum(a,10,17)) 24 cout<<"存在"<<endl; 25 else 26 cout<<"不存在"<<endl; 27 28 cout<<"***************************"<<endl; 29 if(isexnum(a,10,21)) 30 cout<<"存在"<<endl; 31 else 32 cout<<"不存在"<<endl; 33 return 0; 34 }值得注意一下在判断函数中，
if(binary_search(a,a+i,x-a[i])||binary_search(a+i+1,a+n,x-a[i]))把a[i]除掉，不再计入迭代。
使用排序和二分搜索的时间复杂度可以满足题目要求。
但是还有木有更好的算法呢？
注：此题在《编程之美——微软技术面试心得》也有详细的讲解。（2.12 快速寻找满足条件的两个数），这里还提供了另一种搜寻的解法。【2012-10-7附】
转载于:https://www.cnblogs.com/zhuorongtan/archive/2012/09/22/2698437.html
