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
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
i dont understand it..if k is at position an let supposeso 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
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
@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-nextnext 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
