The problem is:
Describe a Θ(n lg n)-time algorithm that, given a set S of n integers and another integer x, determines whether or not there exist two elements in S whose sum is exactly x.
Solution:
1.Sort the elements in S using merge sort.
2.Remove the last element from S. Let y be the value of the removed element.
3.If S is nonempty, look for z= x - y in S using binary search.
4.If S contains such an element z, then STOP, since we have found y and z such that x= y+ z. Otherwise, repeat Step 2.
5.If S is empty, then no two elements in S sum to x.
Step 1 takesΘ(n lg n) time. Step 2 takes Θ(1) time. Step 3 requires at most lg n time. Steps 2–4 are repeated at most n times. Thus, the total running time of this algorithm isΘ(n lg n). The following is my implement code:
Describe a Θ(n lg n)-time algorithm that, given a set S of n integers and another integer x, determines whether or not there exist two elements in S whose sum is exactly x.
Solution:
1.Sort the elements in S using merge sort.
2.Remove the last element from S. Let y be the value of the removed element.
3.If S is nonempty, look for z= x - y in S using binary search.
4.If S contains such an element z, then STOP, since we have found y and z such that x= y+ z. Otherwise, repeat Step 2.
5.If S is empty, then no two elements in S sum to x.
Step 1 takesΘ(n lg n) time. Step 2 takes Θ(1) time. Step 3 requires at most lg n time. Steps 2–4 are repeated at most n times. Thus, the total running time of this algorithm isΘ(n lg n). The following is my implement code:
#include <iostream>
using namespace std;
#define MAX 32767
int S[11]={34,78,346,12,1,55,99,344,3,9,45};
//merge two subarrays A[p...q] and A[q+1...r]
void merge(int a[],int p, int q, int r)
{
int i,j,k;
int* left = new int[q-p+1];
int* right = new int[r-q];
//copy the left and right part of the array
for(i=0;i<q-p+1;i++)
left[i]=a[i+p];
for(j=0;j<r-q;j++)
right[j]=a[j+q+1];
for(i=0,j=0,k=p;k<=r && i<q-p+1 && j<r-q;k++)
{
a[k] = left[i] < right[j]?left[i++] : right[j++];
}
//copy the rest of the array
while(i<q-p+1)
a[k++] = left[i++];
while(j<r-q)
a[k++] = right[j++];
delete[] right;
delete[] left;
}
void merge_sort(int s[], int start, int end)
{
if(start<end)
{
int q=(end+start)/2;
merge_sort(s,start,q);
merge_sort(s,q+1,end);
merge(s,start,q,end);
}
}
int binary_search(int s[], int key, int left, int right)
{
int middle = (left+right)/2;
if(left>right)
return -1;
if(key==s[middle])
return middle;
if(key<s[middle])
return binary_search(s,key,left,middle-1);
if(key>s[middle])
return binary_search(s,key,middle+1,right);
}
int main(int argc, char* argv[])
{
for(int i=0;i<=10;i++)
cout<<S[i]<<" ";
cout<<endl;
merge_sort(S,0,10);
cout<<"After merge sort:"<<endl;
for(i=0;i<=10;i++)
cout<<S[i]<<" ";
cout<<"\nIf the integer you entered is";
cout<<"the sum of two integers which in the";
cout<<" given array,it prints 'yes',";
cout<<" otherwise it prints 'no'!";
int x,z,result=0;
while(1)
{
cout<<"\nNow enter the element:";
cin>>x;
for(i=10;i>0;i--)
{
z=x-S[i];
result = binary_search(S,z,0,i-1);
if(result>=0)
break;
}
if(result>=0)
cout<<"Yes"<<endl;
else
cout<<"No"<<endl;
}
return 0;
}
If you find some errors in the code, pls comment it. Thanks!
Comments
Your code works.
I personally found that the following technique works as well.
First we sort the array using merge sort, which is O(n lg n) in time;
Then, we apply the following procedure
i = 0;
j = n-1; // size of array is n
while (j>i)
if ( a[i] + a[j] == x )
output message and return;
else if ( a[i] + a[j] > x )
--j; // decrease j
else
++i; // increase i;
Each time we reduce the size of the array by 1. So I claim the above procedure is O(n) in time.
Third, totally, it is O( n lgn ) + O (n) = O( n lgn).
Complete code is pasted below and thanks for posting your work.
#include
#include "hjns.h" // for DIM
using namespace std;
void merge(int* a, int p, int q, int r);
void merge_sort(int*a, int p, int r);
void sum(int *a, int n, int x);
int main(int argc, char** argv)
{
int a[] = {1, 4, 9, -10, 8, 5};
int x = -1;
sum(a, DIM(a), x);
return 0;
}
void merge(int* a, int p, int q, int r)
{
int i=p;
int j=q+1;
int k=0;
int* b = new int[r-p+1];
while(i a[i]
while(i b[k++] = a[i++];
while(j b[k++] = a[j++];
for(i=p; i a[i] = b[i-p];
delete [] b;
}
void merge_sort(int*a, int p, int r)
{
int q;
if(p {
q = (p+r)/2;
merge_sort(a, p, q);
merge_sort(a, q+1, r);
merge(a, p, q, r);
}
}
void sum(int *a, int n, int x)
{
int i=0;
int j=n-1;
merge_sort(a, 0, n-1);
while( j>i)
{
if(a[i]+a[j] == x)
{
cout return;
}
else if(a[i]+a[j] > x)
--j;
else
++i;
}
cout }
Posted by: 金海 on May 12, 2007 11:43 PM | Permalink