Idea

We divide a segment into two equal parts and choose the one that contains the solution of the problem using the values of functions.

Algorithm

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

Bounds

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: