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.
