thats what i read somewhere but i wasnt able to do that thats why said .....you have to maintain ... what i think is first check the middle (im supposing that you have three pointers head,tail and middle)... if(greater than that than change head to middle and for middle you have to traverse half of it.... like this i guess....
On Wed, Jul 20, 2011 at 10:08 PM, Ankur Khurana <ankur.kkhur...@gmail.com> wrote: > 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. > -- 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.
