Dicotomic search

The simplest form of sectioning is the dicotomic search: at first iteration the interval $[a,c]$ is divided in two equal parts, $[a,b]$ and $[b,c]$, so that $b = \dfrac{a+c}{2}$; then, choosing $\epsilon>0$, we check if $f(b-\epsilon)>f(b+\epsilon)$. In such case we repeat he whole process with the new interval $[a,b]$, otherwise we repeat with $[b,c]$. It can be proved ([13]) that this method requires $2k$ evaluations of the function $f$, where $k$ is the iterations number. Also the final interval length $I_k = (c_k - a_k)$ is

$$\lim_{k\rightarrow\infty}I_k = \epsilon I_0,$$

where $I_0 = (c-a)$.
So the relative uncertainty on the minimum $x^\star$ is $\epsilon$.