There are 2n+1 neighboring cells in a straight line. An object is in one of all cells except for the cell which locates at the center of all cells, according to a known probability distribution which is assumed to be symmetric with respect to the cell at the center. A searcher is at the cell which locates at the center of all cells at the beginning of the search, and after choosing an ordering of the 2n labels attached to the 2n cells, the searcher examines each cell in that order. An ordering is considered to be optimal when the expected cost of the search is minimized. The cost comprises a traveling cost dependent on the distance from the last cell examined and a fixed examination cost. After basic observations on the present model are made the Bellman’s Principle of Optimality is applied to it. There is then the optimal equation, from which some properties are derived. Approximately optimal search strategies are defined and analyzed. Several discussions are provided.
