About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
Journal of Combinatorial Theory, Series A
Paper
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.