can it be done in O(nlogn) On Sun, Jun 12, 2011 at 8:42 PM, Ashish Goel <[email protected]> wrote:
> once the array is sorted, it is very easy > have two pointers one on left and one on right take the sum, if sum is > greater, move right one inwards else if less than sum, move left one inwards > do this till sum is found of these two pointers meet > > > > Best Regards > Ashish Goel > "Think positive and find fuel in failure" > +919985813081 > +919966006652 > > > > On Thu, Jun 9, 2011 at 11:04 AM, Amit Chauhan > <[email protected]>wrote: > >> 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 >> <[email protected]>wrote: >> >>> we have to find in O(nlgn) >>> >>> >>> On Thu, Jun 9, 2011 at 10:55 AM, D.N.Vishwakarma@IITR <[email protected] >>> > 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 [email protected]. >>> To unsubscribe from this group, send email to >>> [email protected]. >>> 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 [email protected]. >> To unsubscribe from this group, send email to >> [email protected]. >> 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 [email protected]. > To unsubscribe from this group, send email to > [email protected]. > 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 [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
