vizlearn
Home / Algorithms

Fibonacci Search

Algorithms & Data StructuresBy Updated

A comparison-based technique that uses Fibonacci numbers to divide the search space, avoiding costly division operators utilized in Binary or Interpolation search.

Parameters

15

Visualization

Step: 0
Enter a target and click Step or Auto-Run.

Algorithm Insight

Finds the target using Fibonacci sequence intervals:

pos = min(offset + Fm-2, n - 1)
  • 1. Calculate probe position (pos) via the formula.
  • 2. If arr[pos] == target, search is complete!
  • 3. If smaller, shift fib numbers down 1 step & offset = pos. If larger, shift fib numbers down 2 steps.

Efficiency

Time (Avg) O(log N)
Time (Worst) O(log N)

Overview

First choose a Fibonacci number at least as large as the array length. Probe at an offset based on a smaller Fibonacci number, compare the target with that value, and discard the range that cannot contain it. Then use the next smaller Fibonacci offsets for the remaining range.

How it narrows the range

For an array of 10 items, the sequence reaches 13, which covers the array. Each comparison keeps the search within the current bounds. As in binary search, the array must be sorted; otherwise a comparison cannot tell which side to discard.

Set Array Size to 10 and choose a Search Target near the beginning, middle, or end. Press Next Step to follow the probes; use Auto-Run to complete the search, then Reset Array to try another target. The probes are not always at the midpoint because Fibonacci numbers define the split sizes.

Cost and practical use

The Fibonacci sequence grows exponentially, so the number of probes is O(log n), like binary search. Fibonacci search can compute probe positions with additions and subtractions after setting up the sequence, rather than calculating a midpoint by division. This mattered on some older or constrained hardware. On modern general-purpose systems, binary search is usually the simpler default, and Fibonacci search is not generally faster.

The uneven split does not make it an external-memory search method. For data stored in disk pages, structures such as B-trees are designed to reduce page reads.

Common mistakes with Fibonacci Search

  • Searching unsorted input: the range-discard step is no longer valid.
  • Probing outside the array: clamp or guard each index against the current bounds.
  • Treating it as an optimization by default: benchmark on the target hardware and data before replacing binary search.

Sources and next steps

Run it in Python

Binary search's split points come from a division. These come from the Fibonacci sequence, so the whole search runs on addition and subtraction — the reason it exists.

fibonacci_search.pyPython 3
Output
How the code works
  1. while fib < n: f2, f1 = f1, fib; fib = f2 + f1Walks up the sequence 1, 2, 3, 5, 8, 13 ... until it covers the array. Everything afterwards walks back down the same sequence, which is why no arithmetic beyond addition is ever needed.
  2. i = min(offset + f2, n - 1)The probe sits f2 past the part already ruled out. The clamp handles the array being shorter than the Fibonacci number that covers it — the sequence overshoots by design.
  3. fib, f1, f2 = f1, f2, f1 - f2The target is to the right, so the search moves one place down the sequence and offset remembers the discarded prefix. Three subtractions, no division.
  4. fib, f1, f2 = f2, f1 - f2, f2 - (f1 - f2)The target is to the left, so the window shrinks by two places instead of one. The uneven split is why Fibonacci search is not simply binary search with extra steps — it is deliberately lopsided.
  5. if f1 and a[offset + 1] == target:When fib reaches 1 there is at most one unchecked element left. Dropping this check loses exactly one array position, which is a classic way to get an almost-correct implementation.
Change one thing
  • Print len(data) against the number of steps for several targets. It tracks log n, same as binary search — the win was never in the step count.
  • Add an eleventh element and re-run. The first Fibonacci number covering the array jumps, and the probe pattern changes completely.
  • Search for a value that is not in the list. Follow how offset and fib converge until the loop condition fails.
Where this runs
Real CPython, compiled to WebAssembly and running on your own machine — nothing is uploaded. The first run takes a few seconds while the interpreter downloads; after that it is immediate. Need more room, or want to paste your own attempt? Use the Python compiler.




Predict, then reveal
About to run: set Array Size to its maximum (30). Before it does — what happens to the readout?
Committing to an answer first is the point — the reveal runs the experiment on the visualisation above and reads the real value back, so nothing here is scripted.
Check yourself
0 of 3
Answer without scrolling back up.
  1. What does Fibonacci search avoid that binary search needs?
  2. Its step count compared with binary search is:
  3. Why does the probe use min(offset + f2, n - 1)?





 Cheat sheet
Fibonacci Search
Divide a sorted array using Fibonacci numbers rather than midpoints, avoiding the division binary search relies on.
ALGORITHMS · vizlearn.in/dsa/fibonacci_search.html
More in Algorithms
AlgorithmsBubble SortAlgorithmsSelection SortAlgorithmsInsertion SortAlgorithmsRecursion and the Call Stack
About the author
Ashish Jangra builds and maintains VizLearn. Every module here is written and the visualisation behind it hand-built, so the numbers in a readout come from the same code that draws the picture. Corrections are genuinely welcome and get priority over everything else — if a page states something wrong, or an animation misrepresents what the algorithm does, get in touch.
About VizLearnGitHubLinkedInContact