Hi,
For x = 10,11,12,13.... it is going in infinite loop.
Your recursive call for binary_search function is going in infinite loop. So
please look in to the logic for binary search function.
And one more thing once you sort the array and after this you can search the
pair in linear time { for searching the element}.
***Thanks and Regards
*
*Amit K Chauhan*
*
........................................................................................................
There is always, always, always something to be thankful for !!
........................................................................................................
*
On Thu, Jun 9, 2011 at 10:57 AM, D.N.Vishwakarma@IITR <deok...@gmail.com>wrote:
> 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.
>
--
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.
