Dichotomous Search for Random Objects on an Interval

A set of objects to be searched is represented by a set of points lying in an interval of integers. We wish to identify these points within unit-intervals through a dichotomous search, minimizing the expected cost of the search.

The optimal search strategy may depend on the information gained at each stage of the search. It is shown here that for some cases there exists a common optimal strategy. This strategy is generally different from the bisection procedure, and is independent of the number of objects in the interval. As a matter of fact, at each stage of the search a partition of the interval is given and the only information needed for searching a subinterval of this partition is that it still contains an unidentified point.