# Dichotomous search

This finds the maximum of a unimodal function on an interval, $LaTeX: (a, b)$, by evaluating points placed near the center, approximating the bisection method. With $LaTeX: \varepsilon$ being a small positive value, let $LaTeX: x = (a+b)/2 - \varepsilon$ and $LaTeX: y = (a+b)/2 + \varepsilon$. Then, if $LaTeX: f(x) < f(y)$, the new interval of uncertainty is $LaTeX: (x, b)$; if $LaTeX: f(x) > f(y)$, it is $LaTeX: (a, y)$; if $LaTeX: f(x) = f(y)$, it is $LaTeX: (x, y)$. With $LaTeX: N=2M$ function evaluations, the interval of uncertainty can be reduced to within $LaTeX: (b-a)r$, where
$LaTeX: r = 2^{-M} + [1 - 2^{-M}]\varepsilon$.
The same reduction occurs with $LaTeX: N=2M+1$, as an even number of evaluations is required. For example, with $LaTeX: N=20$, $LaTeX: 2^{-10}=0.0009765$, so the interval reduction is $LaTeX: 0.0009765 + 0.999756\varepsilon$. See fibonacci search   for a more efficient method.