we have to find in O(nlgn)
On Thu, Jun 9, 2011 at 10:55 AM, D.N.Vishwakarma@IITR <deok...@gmail.com>wrote:
> #include<iostream>
> using namespace std;
> void merge(int A[],int p,int q,int r)
> {
> int n1=q-p+1;int n2=r-q;
> int L[n1];
> int R[n2];
> for(int i=0;i<n1;i++)
> L[i]=A[p+i];
> for(int j=0;j<n2;j++)
> R[j]=A[q+j+1];
> int i=0,j=0,k;
>
> for(k=p;k<r;k++)
> {
> if((L[i]<=R[j])&&i<n1)
> {A[k]=L[i];i++;}
> else
> {A[k]=R[j];j++;}
> }
>
> for(;i<n1;i++)
> {A[k]=L[i];k++;}
>
> for(;j<n2;j++)
> {A[k]=R[j];k++;}
>
> }
>
> //Merge Sort
> void merge_sort(int A[],int p,int r)
> {
> int q;
> if(p<r)
> {
> q=(p+r)/2;
> merge_sort(A,p,q);
> merge_sort(A,q+1,r);
> merge(A,p,q,r);
> }
> }
>
> //binary search
> int binary_search(int A[],int left,int right,int val)
> {
> int result;
> int mid=(left+right)/2;
> if((right-left)==1&&val!=A[mid])
> result=-1;
> if(val<A[mid])
> result=binary_search(A,left,mid-1,val);
> else if(val>A[mid])
> result=binary_search(A,mid+1,right,val);
> else
> result= mid;
> return result;
> }
>
>
> //main function
> int main()
> {
> int A[]={3,2,4,6,5,7};
> merge_sort(A,0,5);
> for(int i=0;i<6;i++)
> cout<<A[i]<<" ";
> cout<<endl;
> int x;
> cout<<"Enter value of x(=sum of two items in array)"<<endl;
> cin>>x;
> int pos;int flag=0;int i;
> for( i=0;i<6;i++)
> {
> if((x-A[i])>0&&(pos=binary_search(A,i+1,5,x-A[i]))>=0)
> {flag=1;break;}
> }
> if(flag)
> {
> cout<<"There are two whose sum is equal to given number"<<endl;
> cout<<"Those numbers are "<<A[i]<<" and "<<A[pos]<<endl;
> }
> else
> cout<<"There are no such two numbers"<<endl;
>
> return 0;
> }
>
>
> --
> **With Regards
> Deoki Nandan Vishwakarma
> IITR MCA
> *
> *
>
>
--
**With Regards
Deoki Nandan Vishwakarma
IITR MCA
*
*
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
