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.
