@amit only if array is sorted On Sun, Jun 12, 2011 at 11:01 PM, amit kumar <[email protected]>wrote:
> can it be done in O(n) > > > On Sun, Jun 12, 2011 at 11:00 PM, amit kumar <[email protected]>wrote: > >> 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. > -- Sunny Aggrawal B-Tech IV year,CSI Indian Institute Of Technology,Roorkee -- 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.
