@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 at
http://groups.google.com/group/algogeeks?hl=en.
