A DICHOTOMOUS SEARCH
Satoru Murakami · 1971
An object to be searched is represented by a point lying in an interval with uniform a priori probability density. The only available test is to select a point and find out whether the point lies to the left or to the right (with different associated costs) of the test point. In this paper. it is assumed that each test is made at one of n equally spaced points in the whole interval. The problem is that of determining a sequence of test points so as to minimize the expected cost required until the object is located within a unit interval. By use of the dynamic programming approach. the exact solution is derived. and its asymptotic formula with considerably good accuracy is obtained. A comparison of the approximate solution obtained by Cameron and Narayanamurthy with ours is aL,>o given.