the position of the searching element is fixed i guess as it a sorted one......so you will find that elemnt at that vary position without considering how many new elements are added ar going to be added.... and @pankaj i agree we usually dont have one pointer , that is what i asked in my first post but still it would still be difficult to maintain it.... you can do binary search on LL also if we can maintain external node to the middle ...but that is not the thing we should do
On Wed, Jul 20, 2011 at 7:37 PM, saurabh singh <saurabh.n...@gmail.com> wrote: > I think the novelty of this is that we are avoiding the comparison of new > element with all the members of data in LL > > On Wed, Jul 20, 2011 at 7:27 PM, Ankur Khurana <ankur.kkhur...@gmail.com> > wrote: >> >> @Popli : Bingo , that is what i was thinking and mentioned in my previous >> post...... >> >> On Wed, Jul 20, 2011 at 7:08 PM, Gaurav Popli <abeygau...@gmail.com> >> wrote: >>> >>> i want to ask one thing...the way some are saying first check with 2 >>> then 4 and then 16....to reach at that place we are suppose to >>> traverse it and also hav eto put a condition say like count<n or >>> something...in this case also we are comparing so whats the >>> use....correct me if im wrong..... >>> >>> On Wed, Jul 20, 2011 at 6:58 PM, bittu <shashank7andr...@gmail.com> >>> wrote: >>> > can be done in O(n) find tow nodes from starting position find two >>> > nodes p,q such that p < k & k < q as linked list is sorted we have to >>> > keep going on in right direction complexity will no less then O(N) as >>> > its linked list there is no notion of binary search sorted linked list >>> > think out why ? >>> > >>> > only think we can apply some logic to reduce the comparisons that's i >>> > also think will be gr8 improvement but approach sounds good if start >>> > comparing the nodes value using multiple of 2 fact .e.g. take an >>> > integer i=2^j & from j=0 to start comparing 2^0th node, 2^1th node, >>> > 2^2th node....2^jth node might be we are able to reduce the number of >>> > comparisons >>> > >>> > do notify me via gmail if i am wrong if u find difficulty in TC ? else >>> > happy learning >>> > >>> > if this would have been sorted array then we could have been solved it >>> > O(logn) suing same approach. >>> > >>> > >>> > Thanks >>> > Shashank Mani >>> > Computer Science >>> > Birla Institute of Technology, Mesra >>> > >>> > -- >>> > 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. >>> >> >> >> >> -- >> Ankur Khurana >> Computer Science , 4th year >> Netaji Subhas Institute Of Technology >> Delhi. >> >> -- >> 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. > > > > -- > Thanks & Regards, > Saurabh > > -- > 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.
