We divide a segment into two equal parts and choose the one that contains the solution of the problem using the values of functions.
def binary_search(f, a, b, epsilon): c = (a + b) / 2 while abs(b - a) > epsilon: y = (a + c) / 2.0 if f(y) <= f(c): b = c c = y else: z = (b + c) / 2.0 if f(c) <= f(z): a = y b = z else: a = c c = z return c
The length of the line segment on -th iteration:
For unimodal functions, this holds if we select the middle of a segment as an output of the iteration :
Note, that at each iteration we ask oracle no more, than 2 times, so the number of function evaluations is , which implies:
By marking the right side of the last inequality for , we get the number of method iterations needed to achieve accuracy: