A searcher, whose maximal velocity is one, starts from the origin and wishes to discover the hider in minimal expected time.
The linear search problem for a general probability distribution is unsolved.
[7] The linear search problem was solved by Anatole Beck and Donald J. Newman (1970) as a two-person zero-sum game.
This solution was obtained in the framework of an online algorithm by Shmuel Gal, who also generalized this result to a set of concurrent rays.
[9] The best online competitive ratio for the search on the line is 9 but it can be reduced to 4.6 by using a randomized strategy.