there is an infinite line.you are standing at a particular point you can either move 1 step forward or 1 step backward.you have to search for an object in that infinite line.your object can be in any direction. Give optimal algorithm.
2 Likes
@mseghal That approach is pretty slow. If the item si at 10 you wil do a lot of steps. The number of steps is roughly proportional to |X|^2 where X is the position of the point on the Ox line (you can rotate the line to match the Ox). A better algorithm works as follows:
From 0 go 1 step forward, 2 backward, 4 forward, 8 backward, … and so on. You’ll do at most 4|X| steps to find the object which is the best complexity you could achieve because its O(|X|) and you can not do better than that.
1 Like
You got to have some hueristic search somewhere or some more constraints. Otherwise, no hope I guess.
From zero; move to 1 then towards -1 then 2 then -2 then 3 and so on…
Move to 1
Move to -1
Move to 2
Move to -2
Move to 4
Move to -4
Move to 8
Move to -8
and so on, until you find your item.
even second type of binary search is possible. Move to 1, -2, 4, -8, 16 etc. But I’m not sure which gives you less steps and I’m too lazy to count it 
From what i can see my approach is a little better on average versus yours. (by some small percentange about 10%).
yes it’s possible. But these two approaches are only one, you should try at first.
So i did a small benchmark. Both algorithms for N up to 100.000 calculating the average ratio (number of steps divided by |X| where X is the position).
For 1 million mine is 5.4089 and yours is 5.21163 and that seems to be the real ratio as |X| grows. Yours also does better for up until a few thousands where mine becomes better for up until 200.000.
But these doesn’t measures spikes so I also calculated it with the quadratic mean(adding the squared ratios and extracted the square root in the end) and the same with the power of 3.
For quadratic sums I have : 5.6757 and you have 5.4667.
For powers of 3 I have 5.9285 and you have 5.712. From this we can infer that your solution is better in practice as the limit goes to infinity. Sorry for presuming otherwise.
1 Like