Optimal sequential and parallel seach for finding a root

Abstract

Given n opportunities to evaluate a function which is known to have a root in the unit interval, how should these evaluations be used to specify the smallest possible interval containing that root? If f(x) is continuous the answer is the well-known method of binary search and the smallest interval has length ( 1 2)n. The authors solve this optimal search problem in the case of a sequential and a parallel search for the class of functions whose divided differences are bounded above by a number M and below by a number m (m > 0). It is shown that in the sequential case the best interval has length { 1 2[1 - ( m M)]}n. For the optimal search in the parallel case r parallel evaluations are shown to be equivalent to approximately 1 + log r sequential evaluations. © 1977.