@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.-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
> > 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.
