How can you do a binary search if you maintain a pointer to middle ? On Wed, Jul 20, 2011 at 9:58 PM, Gaurav Popli <abeygau...@gmail.com> wrote:
> 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. > > -- 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.
