The problem is as follows: given black box access to a strictly quasiconvex (or unimodal) function $f$ on an interval, say [0, 1], query $f$ repeatedly at various points to find a subinterval containing the minimum. After $n$ queries to $f$, if the interval's length is reduced by a factor of $t$, the algorithm's score is $\sqrt[n]{t}$, which is the amortized factor by which each query to $f$ reduces the length of the interval.
For example, standard ternary search starts with $f(0)$ and $f(1)$, additionally queries $f(\frac{1}{3})$ and $f(\frac{2}{3})$, and obtains a subinterval with size $\frac{2}{3}$. It then iterates and each subsequent iteration starts with $f$ evaluated at the endpoints of the subinterval and reduces the subinterval's length by a factor of $\frac{2}{3}$. Thus the score is $\sqrt{\frac{2}{3}}$.
A better ternary search instead queries at $\frac{1}{2}-\varepsilon$ and $\frac{1}{2}+\varepsilon$ and iterates for a score of $\sqrt{\frac{1}{2}+\varepsilon}$.
An even better algorithm is "pentanary search", starting with $f(0)$, $f(\frac{1}{2})$, and $f(1)$ and querying $f(\frac{1}{4})$ and $f(\frac{3}{4})$ to obtain a subinterval that is the first, middle, or last half of $[0, 1]$. It then iterates. The key is that 3 points from each iteration can be used in the next. Thus the score is $\sqrt{\frac{1}{2}}$.
The best I know of, "golden search", starts with $f(0)$, $f(1)$, and either $f(1-\frac{1}{\phi})$ or $f(\frac{1}{\phi})$, querying for the other of those two, where $\phi$ is the golden ratio. The subinterval is either $[0, \frac{1}{\phi}]$ or $[1-\frac{1}{\phi}, 1]$ and 3 values from the previous iteration can be reused, achieving a score of $\frac{1}{\phi}$.
Can we do better than "golden search"? Do we know the optimal score for this problem?
