Fibonacci Search

A more sophisticated algorithm is the Fibonacci search, where at each iteration the length of the interval is chosen according to the Fibonacci rule: $I_{k-3} = I_{k-2}+I_{k-1}$. This method has the advantage that the uncertainty after n iteration is known a priori: defining the initial interval $I_0 = I_1 = (c-a)$, then

$$I_k =\frac{I_1+f_{k-2}\epsilon}{f_k}$$

where $f_i$ is the $i$-th number of the Fibonacci sequence.
The number of function evaluations are again $2k$, and the disadvantages of this methods are that $\epsilon$ and $n$ must be chosen a priori.