@Swathi read it again its linked list.....using binary search is very costly here :)
@Gaurav sorry i forget the position counter in my algo... if ptr2=ptr1->next....next 10 times do then increment counter by 10 mean we are skipping 10 positions at a time and as it is listed that it is sorted then we can compare ptr2->data with the k if k is greater then ptr2->data we will traverse ptr1 upto ptr2 or untill we find the solution and before doing this make counter-=10; and then increase it by 1 after moving ptr1 by 1 position Still have any doubt? On Mon, Jul 18, 2011 at 10:44 PM, Swathi <[email protected]> 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 <[email protected]>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 <[email protected]> >> 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 <[email protected]> >> 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 <[email protected]> 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 [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. >> >>> >> >> >> >> >> >> >> >> -- >> >> 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 [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. > -- **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 [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.
