Fibonacci Search Technique

Fibonacci search technique is a comparison-based divide-and-conquer algorithm within computation and algorithms for locating a target key x inside a sorted array A[0 .. n − 1] (or finding the extremum of a discrete unimodal function) by successively partitioning the candidate search interval according to consecutive Fibonacci numbers. Originating in Jack Kiefer's 1953 minimax optimal sequential search for the maximum of a unimodal function and adapted to ordered table lookup by David E. Ferguson in 1960 in Communications of the ACM, the algorithm divides a search range of length F_k − 1 into two unequal sub-intervals of lengths F_k−1 − 1 and F_k−2 − 1 around the split offset F_k−1 − 1 (or symmetrically F_k−2 − 1).

Unlike classical binary search, which computes midpoints via integer division by 2 or bitwise right shifts, Fibonacci search updates its probe offsets and step increments using only integer addition and subtraction (since F_k−3 = F_k−1 − F_k−2). Because the ratio of consecutive Fibonacci numbers converges to the golden ratio φ = (1 + √5) / 2 ≈ 1.618034, each comparison shrinks the remaining candidate interval by a factor of either 1 / φ ≈ 0.618 or 1 / φ² ≈ 0.382, completing in at most k − 1 ≈ log_φ(√5 · n) ≈ 1.4404 log₂ n worst-case comparisons and approximately 1.055 log₂ n average comparisons while requiring O(1) auxiliary workspace.

Fibonacci Partitioning of an Interval of Size Fk − 1

Define the standard Fibonacci sequence by the initial conditions F₀ = 0, F₁ = 1, and the second-order linear recurrence:

generating the sequence 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, …. Observe that subtracting 1 from both sides of the Fibonacci recurrence and rearranging yields the precise interval-splitting identity:

Consequently, any contiguous sorted subarray containing exactly m = F_k − 1 elements (for k ≥ 2) can be partitioned around a single interior pivot element into:

1. A left sub-interval of length F_k−2 − 1 elements,
2. The pivot element itself (1 element), and
3. A right sub-interval of length F_k−1 − 1 elements.

Both resulting sub-intervals again have lengths of the precise form F_j − 1 (specifically for j = k − 2 and j = k − 1), allowing the invariant to be maintained inductively all the way down to base intervals of length F₁ − 1 = 0 without ever rounding a fractional quotient.

Kiefer's Unimodal Minimax Optimality vs. Ferguson's Table Lookup

Historically, Fibonacci partitioning arose independently in two closely related settings:

• Kiefer's minimax unimodal optimization (1953): Given a real-valued function f that is unimodal (rising to a single peak and then falling) on an interval [a, b] and a fixed budget of N function evaluations, Jack Kiefer proved that placing the first two interior probes at fractional coordinates F_N−1 / F_N+1 and F_N / F_N+1 is uniquely minimax optimal: after comparing f at those two points, one sub-interval is discarded while the surviving probe already sits at the precise Fibonacci split coordinate for the remaining N − 1 evaluations, shrinking the uncertainty interval by a factor of 1 / F_N+1.
• Ferguson's ordered-table search (1960): In a sorted array A[0 .. n − 1] with a target key x, a single three-way comparison between x and A[i] (testing whether x < A[i], x = A[i], or x > A[i]) determines which side of index i contains x, so only one probe per step is required.

Given a 0-indexed sorted array A[0 .. n − 1] of length n ≥ 1 and a search key x, Fibonacci search avoids maintaining a lookup table of Fibonacci numbers by generating three rolling registers on the fly:

1. Initialization (finding the smallest F_k ≥ n): Set F_k−2 ← 0, F_k−1 ← 1, and F_k ← F_k−2 + F_k−1 = 1. While F_k < n, advance the triple via addition: F_k−2 ← F_k−1, F_k−1 ← F_k, and F_k ← F_k−2 + F_k−1. Initialize the eliminated prefix tracker offset ← −1.
2. Main elimination loop: While F_k > 1:
   • Compute the candidate probe index i ← min(offset + F_k−2, n − 1) (clamping to n − 1 handles array sizes n that are not of the form F_k − 1, equivalent to padding A virtually with +∞ up to length F_k − 1).
   • Case 1 (A[i] < x — step right by one Fibonacci order): The left sub-interval of size F_k−2 is eliminated. Advance offset ← i, and shift the Fibonacci registers down by one index using subtraction: F_k ← F_k−1, F_k−1 ← F_k−2, and F_k−2 ← F_k − F_k−1.
   • Case 2 (A[i] > x — step left by two Fibonacci orders): The right sub-interval of size F_k−1 is eliminated, while offset remains unchanged. Shift the Fibonacci registers down by two indices using subtraction: F_k ← F_k−2, F_k−1 ← F_k−1 − F_k−2, and F_k−2 ← F_k − F_k−1.
   • Case 3 (A[i] = x): Return index i.
3. Final singleton check: If F_k−1 = 1 and offset + 1 < n and A[offset + 1] = x, return offset + 1; otherwise return not found.

Notice that throughout Phase 2, every update to the Fibonacci triple uses only register moves and integer subtractions—never multiplication, division, or bit shifting.

Worst-Case Path vs. Average-Case Path in the Fibonacci Decision Tree

By Binet's formula, the k-th Fibonacci number satisfies:

where φ = (1 + √5) / 2 ≈ 1.6180339887 is the golden ratio and ψ = (1 − √5) / 2 ≈ −0.6180339887. Solving F_k ≈ n for the initial index k gives:

In the worst case, every comparison takes the larger branch (Case 1, where x > A[i]), which decrements the Fibonacci index from k to k − 1 by only 1 unit per step. Thus the deepest root-to-leaf path in the Fibonacci decision tree has depth k − 1 ≈ 1.4404 log₂ n comparisons (roughly 44% more comparisons than binary search in the worst case).

In the average case under a uniform query distribution across all n = F_k − 1 keys, however, the two branches are compensatory:

• With probability F_k−1 / F_k ≈ 1 / φ ≈ 0.6180, the search takes the right branch, which performs 1 comparison and reduces the index by 1 (from k to k − 1).
• With probability F_k−2 / F_k ≈ 1 / φ² ≈ 0.3820, the search takes the left branch, which performs 1 comparison but reduces the index by 2 units (from k to k − 2).

Thus a single comparison reduces the Fibonacci index k by an expected Δk = 1 · (1 / φ) + 2 · (1 / φ²) = (φ + 2) / φ² = (3φ + 1) / (φ + 1) = (5 + √5) / (2√5) ≈ 1.381966 steps per comparison. Dividing the initial index k ≈ 1.44042 log₂ n by the expected index reduction per step yields Knuth's precise average comparison count:

which is within 4.2% of the information-theoretic optimum log₂ n achieved by perfectly balanced binary search.

Donald Knuth analyzed an important physical asymmetry in Fibonacci search: while binary search always leaps across half the remaining interval (⌊m / 2⌋), Fibonacci search moves the read head by F_k−2 ≈ 0.382m in one direction and by F_k−3 ≈ 0.236m in the other. On early rotating magnetic drum memories, magnetic tape units, and modern multi-level CPU caches or external-memory B-tree pages where seek latency increases monotonically with index distance, the average head displacement per probe in Fibonacci search is smaller than in binary search.

Furthermore, when evaluating a convex or unimodal objective function in numerical optimization (where each function evaluation is an expensive simulation or physical measurement and derivatives are unavailable), binary search cannot determine which half of [a, b] contains the minimum from a single midpoint sample; it must evaluate two closely spaced points around the midpoint at every step (requiring 2 log₂(L / ε) evaluations). Kiefer's Fibonacci search reuses the surviving interior sample from the previous step as one of the two interior points of the new interval, reducing the required number of function evaluations to 1.44 log₂(L / ε)—a 28% reduction in total oracle evaluations over dichotomous binary search.

Why was avoiding division by 2 important when Ferguson published Fibonacci search in 1960?

Many first- and second-generation commercial computers of the late 1950s and early 1960s (such as decimal-coded business mainframes and minimal microcontroller architectures) lacked single-cycle arithmetic right-shift instructions on index registers and executed integer division via multi-cycle microcode subroutines. Because Fibonacci search computes every index offset using only addition and subtraction of pre-existing register values, its inner loop ran with lower instruction latency than midpoint division on those architectures.

What happens when the array length n is not equal to Fk − 1?

The algorithm initializes F_k to the smallest Fibonacci number satisfying F_k ≥ n + 1 (or F_k ≥ n in the clamped variant) and clamps every candidate probe index i = min(offset + F_k−2, n − 1) to the last valid array index n − 1. Clamping is mathematically equivalent to padding the array at indices n, n + 1, …, F_k − 2 with virtual sentinel keys equal to +∞ without allocating any extra memory.

How does Fibonacci search relate to golden-section search?

Fibonacci search is the discrete, finite-horizon counterpart of golden-section search (introduced by Kiefer in 1953 and popularized by Avriel and Wilde in 1966). When the number of allowed evaluations N is fixed in advance on a discrete grid of F_k − 1 points, Fibonacci ratios F_k−1 / F_k achieve precise minimax optimality; when N is unspecified on a continuous real interval, taking the limit k → ∞ replaces the rational ratio F_k−1 / F_k with the constant golden ratio conjugate 1 / φ = (√5 − 1) / 2 ≈ 0.618034.

1. Kiefer, J. (1953). "Sequential minimax search for a maximum." Proceedings of the American Mathematical Society, 4(3), 502–506. https://doi.org/10.2307/2032161
2. Ferguson, D. E. (1960). "Fibonaccian searching." Communications of the ACM, 3(12), 648. https://doi.org/10.1145/367487.367496
3. Overholt, K. J. (1973). "Efficiency of the Fibonacci search method." BIT Numerical Mathematics, 13(1), 92–96. https://doi.org/10.1007/BF01933527
4. Knuth, D. E. (1998). The Art of Computer Programming, Volume 3: Sorting and Searching (2nd ed., Section 6.2.1: "Fibonaccian search," pp. 417–422). Addison-Wesley. https://cs.stanford.edu/