Revisiting the Problem of Searching on a Line

Jean-Lou De Carufel

We revisit the problem of searching for a target at an unknown location on a line when given upper and lower bounds on the distance D that separates the initial position of the searcher from the target.

We present tight bounds on the exact optimal competitive ratio achievable, parameterized in terms of the given range for D, along with an optimal search strategy that achieves this competitive ratio.

This is joint work with Prosenjit Bose and Stephane Durocher.