# 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: