Here is the idea I was thinking of: - start from the root: if(root->data < k) move to position 2 in the list. - in this way every time move the pointer to the position double the current position and compare th eelement of node with k( moving here is form 1 - 2 , 2-4, 4-8 ,8-16 ......) - suppose you found a certain node at position n whose node->data > k , then now u only have to search for k between index n/2 to n (i.e. if you found 16th element >k then search for k between 8th and 16ht element)..
correct me if any flaws..... On Jul 19, 3:38 am, Dumanshu <duman...@gmail.com> wrote: > @Gaurav: Ever Increasing means that you don't know the length of the > list. So you have to assume some index n, traverse the list upto that > point and check the results. If not found increment the n to some > higher value. > We are basically trying to improve the complexity by taking higher and > higher jumps for n. > > On Jul 19, 2:03 am, Gaurav Popli <abeygau...@gmail.com> wrote: > > > > > > > > > yeah...im saying to reach position n at which k is placed we have to > > trverse n positions from head or not...?? > > and i didnt understand the use of ever increasing...please elaborate on it.. > > > On Tue, Jul 19, 2011 at 2:08 AM, Dumanshu <duman...@gmail.com> wrote: > > > @Swathi: plz give the TC of ur algo (exponential plus log) > > > > On Jul 18, 10:14 pm, Swathi <chukka.swa...@gmail.com> wrote: > > >> The solution to this problem will be a combination of exponential > > >> increase > > >> and the binary search.. > > > >> start = 0; > > >> end = 0; > > >> index =0; > > >> middle = 0; > > >> while (1) > > >> { > > >> if(a[start] == data) > > >> return start; > > >> if(a[end] == data) > > >> return end; > > >> if(data > end) > > >> { > > >> start = end; > > >> end = pow(start,2); // here we are consider exponential for faster > > >> search. > > >> // no need to check any boundary conditions as the array is infinite > > >> continue; > > >> } > > >> else > > >> { > > >> // do binary search between start index and end index because data is > > >> inbetween a[start] and a[end] > > >> } > > > >> } > > > >> Hope this helps... > > > >> On Mon, Jul 18, 2011 at 10:32 PM, Gaurav Popli > > >> <gpgaurav.n...@gmail.com>wrote: > > > >> > i dont understand it..if k is at position an let suppose....so to > > >> > check at that position dont you have to traverse till that position > > >> > ...is thr anything else than the head of list...??or i understood > > >> > wrongly...?? > > > >> > On Mon, Jul 18, 2011 at 9:55 PM, sagar pareek <sagarpar...@gmail.com> > > >> > wrote: > > >> > > Update on 2nd line > > > >> > > 2. if( ptr2=ptr1->next->next.......(5 or 10 times) ) goto 3. > > >> > else > > >> > > make linear search till NULL encounter and exit with the solution > > > >> > > On Mon, Jul 18, 2011 at 7:41 PM, sagar pareek <sagarpar...@gmail.com> > > >> > wrote: > > > >> > >> i have one approach :- > > > >> > >> first compare root->data and k > > >> > >> if k is very much greater than root->data then set next=5or10 ur > > >> > >> choice > > > >> > >> else set next 2or3 ur choice > > >> > >> take two pointers ptr1 and ptr2 > > > >> > >> now lets take k is much greater than root->data > > >> > >> then > > >> > >> 1. set ptr1=root //initially > > >> > >> 2. if( ptr2=ptr1->next->next.......(5 or 10 times) ) else make > > >> > >> linear > > >> > >> search till NULL encounter > > >> > >> 3. if ptr2->data==k return its position > > >> > >> 4. else if (ptr2->data>k) set ptr1=ptr2 goto 2 > > >> > >> 5. else traverse the ptr1 upto ptr2, if found return its position > > >> > >> else > > >> > >> return fail > > > >> > >> if anyone has more efficient solution then pls tell :) > > >> > >> On Mon, Jul 18, 2011 at 6:53 PM, Dumanshu <duman...@gmail.com> > > >> > >> wrote: > > > >> > >>> You have a sorted linked list of integers of some length you don't > > >> > >>> know and it keeps on increasing. You are given a number k. Print > > >> > >>> the > > >> > >>> position of the number k. > > >> > >>> Basically, you have to search for number k in the ever growing > > >> > >>> sorted > > >> > >>> list and print its position. > > > >> > >>> Please write the complexity of whatever solution you propose. > > > >> > >>> -- > > >> > >>> 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. > > > >> > >> -- > > >> > >> Regards > > >> > >> SAGAR PAREEK > > >> > >> COMPUTER SCIENCE AND ENGINEERING > > >> > >> NIT ALLAHABAD > > > >> > > -- > > >> > > Regards > > >> > > SAGAR PAREEK > > >> > > COMPUTER SCIENCE AND ENGINEERING > > >> > > NIT ALLAHABAD > > > >> > > -- > > >> > > 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.-Hidequoted text - > > > >> - Show quoted text - > > > > -- > > > 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 > > > athttp://groups.google.com/group/algogeeks?hl=en.-Hide quoted text - > > > - Show quoted text - -- 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.