Fibonacci Search

How do you find the highest point on a mountain range shrouded in fog, using the fewest possible measurements? This classic problem of finding an optimum value with limited information is central to many challenges in science and technology. The core challenge lies in creating a search strategy that is both efficient and guaranteed to succeed. This article addresses this by exploring the Fibonacci search, a remarkably powerful and elegant algorithm designed for this very purpose. We will uncover how this method provides the best possible solution when the number of attempts is known beforehand.

The journey begins in the ​​Principles and Mechanisms​​ chapter, where we will dissect the algorithm's inner workings. We'll start with the foundational idea of bracketing an optimum and see how the desire to reuse information leads to strategies based on the golden ratio and, ultimately, the Fibonacci sequence. We will prove why Fibonacci search is the undisputed champion for a fixed budget and explore its surprising connection to real-world hardware performance, including CPU caches and memory latency. Following this, the ​​Applications and Interdisciplinary Connections​​ chapter will broaden our perspective, showcasing how this single, powerful idea finds application everywhere—from optimizing robotic arms and chemical reactions to tuning machine learning models and solving abstract computational puzzles. By the end, you will not only understand how Fibonacci search works but also appreciate its status as a fundamental tool for optimization across disciplines.

Imagine you are a treasure hunter on a mountain range shrouded in a thick, persistent fog. Your map tells you that the treasure is buried at the highest peak, but you can only see the ground beneath your feet. You have a special altimeter that can instantly measure the elevation at any point on the mountain range, but each measurement is costly and time-consuming. How do you find the peak with the fewest possible measurements?

This is the essential problem that a whole class of brilliant algorithms, including Fibonacci search, is designed to solve. The only thing we need to assume about our mountain range is that it is ​​unimodal​​—it has only a single peak. If you start walking away from the peak in any direction, you only ever go downhill. This simple property is all the structure we need to devise a remarkably efficient search.

Let's say our mountain range stretches from point $a$ to point $b$. A first, naive thought might be to just sample points at random. But that's terribly inefficient. A much better idea is to use a bracketing strategy. Suppose we take two measurements at points $x_1$ and $x_2$ inside our interval $[a, b]$, with $a \lt x_1 \lt x_2 \lt b$.

If we find that the altitude at $x_1$ is higher than at $x_2$ (i.e., $f(x_1) \gt f(x_2)$), what have we learned? Since we know there is only one peak, and the function's value decreases from $x_1$ to $x_2$, the peak cannot possibly be to the right of $x_2$. If the peak were in the interval $(x_2, b]$, the function values would have to increase towards it from $x_2$, which violates the unimodal property. Thus, the peak must lie somewhere in the interval $[a, x_2]$. In a single move, we've eliminated the entire $(x_2, b]$ region! Similarly, if $f(x_2) \gt f(x_1)$, the peak must be in $[x_1, b]$.

This is progress! But the truly brilliant insight comes when we ask the next question: how should we place $x_1$ and $x_2$ to be as efficient as possible? After we've shrunk our interval to, say, $[a, x_2]$, we will need to pick two new points inside this new interval. But wait—we already have a point there: $x_1$, and we already know its altitude! To save a costly measurement, we should reuse it.

This desire to reuse an old measurement point imposes a beautiful geometric constraint. For the setup to be "self-similar"—that is, for the reused point $x_1$ to be in the correct position for the next stage of the search—the points must be placed according to a very special number. The new interval has a certain length, and the old point $x_1$ divides it into two segments. For the process to repeat perfectly, the ratio of the new interval's length to its larger segment must be the same as the ratio of the larger segment to the smaller one. This condition gives rise to a quadratic equation, $\rho^2 + \rho - 1 = 0$, whose positive solution is $\rho = (\sqrt{5}-1)/2 \approx 0.618$.

This number, you might recognize, is the reciprocal of the ​​golden ratio​​, $\phi$. This strategy is called ​​Golden-Section Search (GSS)​​. At each step, it shrinks the interval by a factor of $\rho$, reusing one point and making only one new measurement. It's a wonderfully elegant method, and it is the best possible strategy if you don't know in advance how many measurements you are allowed to make.

Golden-section search is optimal for an explorer with an unknown budget. But what if you are a planner with a fixed budget? Suppose your funding allows for exactly $N=17$ experiments, and you need to pin down the location of the peak as accurately as possible within those 17 measurements. Can you do better than the steady, fixed-ratio shrinkage of GSS?

The answer is a resounding yes, and the solution is the ​​Fibonacci search​​. It is a testament to the power of planning. It was proven by the mathematician J. Kiefer in 1953 to be the provably optimal strategy for a fixed number of evaluations. No other method can guarantee a smaller final interval of uncertainty in the worst case.

Instead of a constant shrinkage ratio, Fibonacci search uses a dynamic one, cleverly derived from the Fibonacci sequence ($F_1=1, F_2=1, F_3=2, F_4=3, \dots$). If you have a budget of $N$ evaluations, the algorithm places its first two probes using ratios derived from $F_N$. After the first reduction, it proceeds as if it has a budget of $N-1$ evaluations for the new, smaller interval. The shrinkage factor changes at each step, but it is precisely choreographed to give the maximum possible total reduction at the end.

The magic is in the numbers. With a budget of $N$ evaluations, a standard Fibonacci search guarantees a final interval of length $L_0 / F_{N+1}$, where $L_0$ is the initial interval length. Let's compare. To achieve a final interval less than $0.1\%$ of the original, we need a reduction factor greater than 1000. For Fibonacci search, we must find the smallest $N$ such that $F_{N+1} > 1000$. A quick calculation shows $F_{16} = 987$ and $F_{17} = 1597$. Thus, we need $N+1=17$, so $N=16$ evaluations are sufficient, guaranteeing a reduction factor of 1597.

How does GSS fare with 16 evaluations? After $N=16$ evaluations, there have been $N-1=15$ reductions. The final interval length is $L_0 \times \rho^{15} = L_0 \times (1/\phi)^{15} \approx L_0 / \phi^{15}$. Since $\phi^{15} \approx 1364$, GSS only guarantees a reduction to $L_0/1364$. The Fibonacci search reduction factor of 1597 is clearly better. For a fixed budget, Fibonacci search is the undisputed champion.

The deep connection between these two methods is one of the most beautiful results in this area. As the number of planned evaluations $N$ gets very large, the ratio of consecutive Fibonacci numbers, $F_{k-1}/F_k$, famously converges to the golden ratio's reciprocal, $1/\phi$. This means that Golden-Section Search is simply the limiting case of Fibonacci search as the budget goes to infinity! They are not rivals, but two faces of the same underlying principle of optimal search.

This elegant dance of shrinking intervals is not confined to finding peaks of functions. It can be adapted to a seemingly different problem: searching for a specific value in a huge, sorted list of items. This is a task computers perform millions of time a second.

Instead of evaluating a function, we perform a comparison: is our target value greater or less than the element at a chosen index? An "interval" is now a range of array indices. The core idea of reusing information remains. By choosing our probe index based on Fibonacci numbers, we ensure that the boundary of the next sub-problem is an index we've already examined, saving us from re-reading memory.

The mechanics are fascinating. For an array of size $n$, the algorithm works with a Fibonacci number $F_m \ge n$. It probes an index, and based on the comparison, it reduces the problem to a search in a smaller array whose size corresponds to either $F_{m-1}$ or $F_{m-2}$. This recursive structure means that for an array of size $F_k - 1$, the worst-case number of comparisons is a mere $k-2$. The algorithm's behavior is so precise that if we were to only observe the sequence of moves it makes—for example, "right, left, right, left, right"—we could reverse-engineer the internal state of the search and deduce the smallest possible array it could have been exploring. It’s like deducing the dancer from the dance steps left in the sand.

An algorithm on a blackboard is a pure, abstract thing. But an algorithm running on a computer is a physical process, subject to the laws of physics and the constraints of hardware. It is here, in the messy reality of silicon and electrons, that the true character of an algorithm is revealed.

A modern computer's processor (CPU) is blindingly fast, but accessing data from the main memory (RAM) is, by comparison, like a cross-country trip. To bridge this gap, the CPU uses small, fast caches. An algorithm's real-world speed is determined not just by how many operations it does, but by its ​​memory access pattern​​. Does it jump around memory randomly, causing a cache miss (a slow trip to RAM) at every step? Or does it move in a predictable way?

Let's compare Fibonacci search to its cousin, ​​ternary search​​, which splits the interval into three parts and makes two probes. In a simplified model where a memory access is a "hit" only if it's very close to the previous one, we can analyze the cache performance. Ternary search makes two widely spaced probes per iteration, likely causing two cache misses. Fibonacci search makes only one. So Fibonacci should be better, right?

Astonishingly, no. A careful analysis shows that for a large array, the expected number of cache misses for ternary search is proportional to $2\log_3(N)$, while for Fibonacci search it is proportional to $\log_\phi(N)$. When we compare the constants, we find that $2/\ln(3) \approx 1.82$ is less than $1/\ln(\phi) \approx 2.08$. Counter-intuitively, ternary search, despite its two probes, stresses the memory system less than Fibonacci search! This is a powerful lesson: "optimality" is not absolute; it depends entirely on the cost model you care about.

The story gets even more interesting. Modern CPUs can ​​prefetch​​ data they predict will be needed soon. But Fibonacci search is a moving target; its strides change at every step, fooling simple hardware prefetchers. Can we do better with software? The challenge is that we don't know which way the search will go (left or right) until after the current comparison is done. By then, it's too late to issue a prefetch to hide the several hundred cycles of memory latency.

The solution is worthy of a sci-fi movie: we must be speculative. We can predict the most probable path and issue a chain of prefetches deep into the future. How deep? The lookahead depth is determined by the physics of the chip: the memory latency $L$ divided by the computation time per step $c$. If $L=200$ cycles and $c=12$ cycles, we need to issue a prefetch for the data needed 17 steps from now, just to have it arrive in time! This is a high-stakes race between computation and data transfer, a perfect illustration of co-designing algorithms and hardware.

Finally, what if we are on an exotic machine where subtraction is a thousand times slower than addition? Does this penalize Fibonacci search, which seems to need subtractions like $F_{k-2} = F_k - F_{k-1}$? No! This is where we see the difference between an abstract algorithm and its implementation. We can precompute the necessary Fibonacci numbers using only cheap additions and store them in a table. The runtime search loop then involves only table lookups and additions, completely sidestepping the expensive subtractions.

From finding a foggy peak to navigating the intricate memory hierarchy of a CPU, the principles of Fibonacci search reveal a deep unity. It is a story of optimization, of planning, and of the beautiful interplay between abstract mathematical ideas and the concrete physical reality of computation.

Now that we have explored the elegant mechanics of Fibonacci search, we might ask, "What is it good for?" It is a fair question. We have seen it is a wonderfully efficient way to find the top of a hill, so to speak, but where do such hills appear in science and life? The answer, you may be delighted to find, is everywhere. The principle of finding an optimal point in a system that first improves and then declines is a theme that nature, engineering, and even economics seem to love. Fibonacci search, then, is not just a clever piece of code; it is a key that unlocks optimization problems across a spectacular range of disciplines. Let us take a walk through some of these fields and see this beautiful idea at work.

Imagine you are an engineer designing a robotic arm. There is a single joint you can control, an angle $\theta$. Your goal is to find the angle that gives the arm its maximum lifting capacity. It is easy to imagine that at some angles the arm has poor leverage, and at others it is much stronger. It is quite plausible that the capacity is a unimodal function of the angle: the strength increases as the arm moves into a favorable position, and then decreases as it moves past that optimal point. How do you find this perfect angle? You could try every possible angle, but that is slow. You could use calculus if you have a perfect mathematical formula for the capacity, but in the real world, you might only be able to measure it. Here, Fibonacci search (or its continuous cousin, golden-section search) is the perfect tool. By simply testing a few angles and comparing the results, the algorithm can rapidly close in on the optimal angle that maximizes lifting capacity, without ever needing to know the underlying physics equations.

Let's shrink our scale from robots to molecules. In chemistry, many reactions are sped up by a catalyst. A natural question for a chemical engineer is, "What concentration of catalyst gives the fastest reaction rate?" You might think, "the more, the better," but that is not always true. At low concentrations, adding more catalyst increases the rate. However, at very high concentrations, other effects can kick in, such as substrate inhibition, where the catalyst molecules actually start to get in each other's way or bind to the product in unhelpful ways, slowing the reaction down. The result is a reaction rate that is a unimodal function of catalyst concentration. To find the peak of this function—the ideal concentration—we can again turn to Fibonacci search. By running a few experiments at different concentrations chosen by the algorithm, we can efficiently determine the optimal amount of catalyst to use, maximizing yield and minimizing waste. This applies to a wide variety of reaction models, from the classic Michaelis-Menten kinetics to more complex Haldane-type models that explicitly account for inhibition.

The same logic extends to the very modern field of machine learning. When we train a neural network, we have to choose certain "hyperparameters," which are settings that control the learning process itself. One of the most critical is the learning rate. If the learning rate is too low, the model learns agonizingly slowly. If it is too high, the learning process becomes unstable, and the model's performance gets worse. Somewhere in between, there is a "sweet spot"—a learning rate that leads to the best performance in the shortest time. The model's final error, or loss, is often a unimodal function of the learning rate. Finding this optimal rate is a one-dimensional search problem, and since calculating the loss for a given learning rate can be very computationally expensive (requiring training a whole model), we want to do it in as few steps as possible. Fibonacci search is an ideal candidate for this task, allowing data scientists to efficiently tune their models for peak performance.

From optimizing marketing budgets in business, where profit might rise with advertising spend before being outweighed by the costs, to computer graphics, where we might search for the parameter $t$ that finds the point on a complex Bézier curve closest to a user's mouse click, this pattern repeats. Even in abstract settings like game theory, a player might want to find their best response to an opponent's strategy. If their payoff is a unimodal function of their own continuous choice, they can use a Fibonacci-like search to find their optimal move. And in signal processing, if we have a way of scoring how well a pattern matches a larger signal, this score is often unimodal as a function of the alignment offset. Fibonacci search can then find the best possible alignment with a logarithmic number of expensive score calculations.

So far, our "hills" have been functions over continuous or physical quantities. But the same thinking can be applied to more abstract, discrete structures. This is where we see the true versatility of the underlying idea.

Consider this puzzle: you are given an array of numbers that is bitonic. This means the numbers first strictly increase to a peak and then strictly decrease. For example, [1, 5, 9, 12, 10, 8, 3]. The array is not sorted, so you cannot use a standard binary search to find a target value. What do you do? The key is to see that the array's structure is just a discrete unimodal function. The first step is to find the peak! We can use a discrete Fibonacci or ternary search to find the index of the maximum element in $O(\log n)$ time. Once we find the peak, say at index $p$, we have split the problem into two simpler ones: a strictly increasing array from the start to $p-1$, and a strictly decreasing array from $p+1$ to the end. On these two sorted segments, we can use a standard binary (or Fibonacci) search. The problem beautifully illustrates how a unimodal search can be a crucial first step in breaking down a complex problem into familiar, solvable parts.

Let's push the abstraction further. Imagine a circular array of numbers that is a "rotated" unimodal sequence. For example, [9, 16, 25, 40, 30, 20, 12, 7, 3, 1, 4]. There's a peak (40), but the increasing and decreasing parts are wrapped around. How can we find the peak here? A direct application of Fibonacci search won't work because the indices don't correspond to the unimodal ordering. Here, a moment of creative insight is needed. A unimodal sequence, when laid out linearly, must have its minimum value at one of the two ends. When this sequence is rotated to form a circle, that minimum element is now somewhere in the middle. If we can find this global minimum, we can use it as a "seam" to virtually "unroll" the circular array into a linear one that is perfectly unimodal. After this clever transformation, we are back on familiar ground and can use our trusted Fibonacci search to find the peak's position relative to the seam, and then map it back to the original circular array's indices.

Finally, what if the hill is not a one-dimensional line, but a two-dimensional landscape? Consider a 2D matrix where every single row and every single column is a unimodal sequence. This implies there is a single global maximum somewhere in the matrix—a "mountain peak." How can we find it without checking every single cell? We can use our 1D search as a powerful subroutine. Pick the middle row of the matrix. Since this row is unimodal, we can find its maximum element in $O(\log n)$ time using a 1D search. Now, look at that element's neighbors in the column above and below it. If our element is greater than both its vertical neighbors, we have found the global peak! Why? Because it is the maximum in its row, and it's a peak in its column. If, however, the neighbor above it is larger, it tells us the global peak must lie in the upper half of the matrix. If the neighbor below is larger, the peak is in the lower half. In a single step, we have eliminated half of the rows! We can repeat this process, alternating between reducing rows and columns, to zero in on the global maximum with breathtaking efficiency.

From engineering to economics, from chemistry to computation, the signature of unimodality is a signpost for optimization. The Fibonacci search gives us a rigorous and astonishingly efficient method for heeding that signpost. It teaches us that sometimes, the most powerful ideas in science are not the most complex, but are those that capture a simple, recurring pattern in the world and give us a general key to unlock it.