162 1. 给一个有N个整数的数组S..和另一个整数X,判断S里有没有2个数的和为X

/*
1. 给一个有N个整数的数组S..和另一个整数X,判断S里有没有2个数的和为X，
请设计成O(n*log2(n)）的算法。

快排,头尾夹逼.
*/
#include 
#include 
using namespace std;
#define N 100 
typedef pair Pair; 

Pair findSum(int *s,int n,int x) 
{ 
  sort(s,s+n);  //排序 
  int *begin=s,*end=s+n-1;//首尾 
  while(begin  { 
    if(*begin+*end>x) 
      end--;  
    else if(*begin+*end      begin++; 
    else 
      return Pair(*begin,*end); 
  } 
  return Pair(-1,-1); 
} 
int main() 
{ 
  int arr[N]; 
  int n,x,i; 
  while(1) 
  { 
    cout    cin>>n;
    if(n==-1) break;
    cout    for(i=0;i      cin>>arr[i]; 
    cout    cin>>x; 
    Pair ret=findSum(arr,n,x); 
    cout  } 
  return 0; 
} 
/*
8
3 -4 7 8 12 -5 0 9
11
5
1 4 5 -2 3
3
-1

*/