A comparison-based technique that uses Fibonacci numbers to divide the search space, avoiding costly division operators utilized in Binary or Interpolation search.
Overview
Why anyone would avoid the midpoint
Binary search computes mid = (lo + hi) / 2. That division — or at least a bit shift — was genuinely expensive on early hardware, and on some architectures it still is. Fibonacci search finds a comparable split point using nothing but addition and subtraction of precomputed Fibonacci numbers.
The trick rests on a property of the sequence. Since F(k) = F(k−1) + F(k−2), any Fibonacci number splits naturally into two smaller Fibonacci numbers. Use that split as the probe point and both resulting subarrays are themselves Fibonacci-sized, so the same trick applies recursively without ever computing a new boundary from scratch.
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)
Fibonacci Search: A Practical Guide
Binary search without division. It splits the array at Fibonacci boundaries using only addition and subtraction, which mattered enormously on hardware that could not divide.
The mechanism, step by step
First find the smallest Fibonacci number that is at least the array length. For an array of 10 elements the sequence runs 1, 1, 2, 3, 5, 8, 13 — so F(7) = 13, with F(6) = 8 and F(5) = 5.
Probe at offset + F(k−2), clamped to the array bounds. Compare:
Target is larger → discard the left part; shift the Fibonacci numbers down two and move the offset up to the probe.
Target is smaller → discard the right part; shift the Fibonacci numbers down one.
Equal → found.
Every update is an index addition or a step down the precomputed sequence. No division, no multiplication.
The complexity, and the honest comparison
Because consecutive Fibonacci numbers approach the golden ratio φ ≈ 1.618, each step shrinks the search space by a factor of about 1.618 rather than binary search’s 2. So Fibonacci search is O(log n) too, but with a slightly larger constant:
log1.618(n) ≈ 1.44 × log2(n)
Roughly 44% more comparisons. In exchange, the probe positions are computed with additions only, and — the reason it survives in practice — the two subarrays it examines are unequal in size, with the smaller one probed first. On data read from tape or disk in blocks, that uneven split touches fewer distant locations than binary search’s repeated jumps to the exact middle.
Splitting by Fibonacci ratios instead of halves
Fibonacci search finds a value in a sorted array by narrowing the range, like binary search — but it splits using Fibonacci numbers rather than at the midpoint.
The Fibonacci sequence is 1, 1, 2, 3, 5, 8, 13, 21, 34, 55… and consecutive ratios approach the golden ratio, about 0.618. So each step divides the range into parts of roughly 38% and 62% rather than 50/50.
def fibonacci_search(arr, target):
n = len(arr)
fib2, fib1, fib = 0, 1, 1 # fib = fib1 + fib2
while fib < n:
fib2, fib1 = fib1, fib
fib = fib1 + fib2
offset = -1
while fib > 1:
i = min(offset + fib2, n - 1)
if arr[i] < target:
fib, fib1, fib2 = fib1, fib2, fib1 - fib2 # move right
offset = i
elif arr[i] > target:
fib, fib1, fib2 = fib2, fib1 - fib2, fib2 - (fib1 - fib2)
else:
return i
if fib1 and offset + 1 < n and arr[offset + 1] == target:
return offset + 1
return -1
The complexity is O(log n), the same as binary search. The number of comparisons is marginally higher, because the splits are uneven.
Why it exists: no division
The reason for the algorithm is visible in the code above: it uses only addition and subtraction.
Binary search computes mid = lo + (hi - lo) // 2, which needs a division (or a shift). Fibonacci search moves through a precomputed sequence by adding and subtracting.
On hardware without a hardware divide instruction — early processors, some microcontrollers, some digital signal processors — division was expensive enough that avoiding it mattered. That is the historical motivation, and it is largely obsolete: a shift is one cycle on any modern processor.
Binary search
Fibonacci search
Split
50/50
~38/62
Arithmetic
Division or shift
Addition and subtraction
Comparisons
~log₂ n
Marginally more
Complexity
O(log n)
O(log n)
Cache behaviour
Jumps by halves
Smaller first jump
The remaining argument: memory access
There is one non-historical claim worth examining. Fibonacci search's first probe is closer to the start of the array than binary search's midpoint, and subsequent probes cluster more.
On very large arrays where each probe is a cache miss or, worse, a disk read, examining locations that are closer together can touch fewer distinct pages. Binary search's first few probes are maximally spread, which is the worst case for locality.
That effect is real and small, and it is why Fibonacci search occasionally appears in discussions of external searching. In practice, structures designed for the hardware — B-trees, which pack many keys per page — address the problem far more effectively than adjusting the split ratio.
So the honest position: Fibonacci search is a historical curiosity with a marginal locality argument, and binary search is what you should use.
Its genuine value is as an illustration that the same O(log n) behaviour can be achieved by several splitting strategies, and that the constant factors and hardware characteristics decide which is preferred — a point that applies far beyond this algorithm.
A search with no division, and what it actually costs
Fibonacci search exists because binary search needs a division to find the midpoint, and there were machines where division was expensive or absent. It is a genuine algorithm with a genuine motivation, and the honest thing to measure is whether the motivation still applies.
example_01.pyPython
def fib_search(a, target):
n = len(a)
# smallest Fibonacci number >= n
f2, f1 = 0, 1
f = f2 + f1
while f < n:
f2, f1 = f1, f
f = f2 + f1
offset, probes = -1, 0
while f > 1:
i = min(offset + f2, n - 1)
probes += 1
if a[i] < target:
f, f1 = f1, f - f1 # only additions and subtractions
f2 = f - f1
offset = i
elif a[i] > target:
f, f1, f2 = f2, f1 - f2, f2 - (f1 - f2)
else:
return i, probes
if f1 and offset + 1 < n and a[offset + 1] == target:
return offset + 1, probes + 1
return -1, probes
def bin_search(a, target):
lo, hi, probes = 0, len(a) - 1, 0
while lo <= hi:
probes += 1
mid = (lo + hi) // 2 # the division this is all about
if a[mid] == target:
return mid, probes
if a[mid] < target:
lo = mid + 1
else:
hi = mid - 1
return -1, probes
import math
import random
for n in (100, 1000, 10000, 100000):
data = list(range(0, n * 2, 2))
rng = random.Random(n)
targets = [data[rng.randrange(n)] for _ in range(200)]
fb = bp = 0
for t in targets:
fi, fp = fib_search(data, t)
bi, b = bin_search(data, t)
assert data[fi] == t and data[bi] == t, (t, fi, bi)
fb += fp
bp += b
print("n = %6d fibonacci %.2f probes binary %.2f log2(n) = %.1f"
% (n, fb / 200, bp / 200, math.log2(n)))
# Both are logarithmic and the counts are close, with Fibonacci search
# slightly worse. That is expected: it splits the range at roughly 0.618
# and 0.382 rather than in half, and an uneven split costs a little more
# on average than an even one.
#
# What it buys is the arithmetic. Look at the update lines: the Fibonacci
# version moves between consecutive Fibonacci numbers using only addition
# and subtraction, while binary search computes (lo + hi) // 2.
print()
print("operations per step:")
print(" binary: one addition, one shift or division")
print(" fibonacci: two or three additions and subtractions, no division")
# On a modern CPU an integer division is a handful of cycles and a shift
# is one, so binary search wins outright and the original motivation has
# largely evaporated.
#
# The claim usually offered in its defence is that the probe pattern is
# gentler -- shorter seeks, which mattered on tape. That one is worth
# testing rather than repeating:
data = list(range(0, 2000, 2))
_, _ = fib_search(data, 1500)
def probe_positions(a, target, which):
seen = []
n = len(a)
if which == "bin":
lo, hi = 0, n - 1
while lo <= hi:
mid = (lo + hi) // 2
seen.append(mid)
if a[mid] == target:
break
if a[mid] < target:
lo = mid + 1
else:
hi = mid - 1
return seen
f2, f1 = 0, 1
f = f2 + f1
while f < n:
f2, f1 = f1, f
f = f2 + f1
offset = -1
while f > 1:
i = min(offset + f2, n - 1)
seen.append(i)
if a[i] < target:
f, f1 = f1, f - f1
f2 = f - f1
offset = i
elif a[i] > target:
f, f1, f2 = f2, f1 - f2, f2 - (f1 - f2)
else:
break
return seen
b = probe_positions(data, 1500, "bin")
fpos = probe_positions(data, 1500, "fib")
print()
print("indices probed searching a 1000-element array:")
print(" binary: ", b)
print(" fibonacci: ", fpos)
print(" largest jump between consecutive probes -- binary %d, fibonacci %d"
% (max(abs(b[i + 1] - b[i]) for i in range(len(b) - 1)),
max(abs(fpos[i + 1] - fpos[i]) for i in range(len(fpos) - 1))))
# The defence does not survive the measurement. Fibonacci search made the
# LARGER jump here, not the smaller one -- its first two probes straddle
# most of the array before it settles down, while binary search halves
# tidily from the middle. On this input the seek argument is simply not
# true, and it is worth changing the probe target above to see how much
# the comparison depends on which element you look for.
#
# What does survive: the algorithm computes no index outside the array and
# uses no division, which mattered on hardware without bounds checking or
# a divide instruction. Neither applies to an array in memory on a machine
# built in the last forty years. Use binary search -- and know that this
# exists, why it was invented, and that the folklore reason for keeping it
# does not hold up.
Output
Experiments to try
Watch the uneven split. Set Array Size to 30 and press Next Step through a search. Notice the probe does not land in the middle — it sits about 38% of the way in, which is 1/φ². Binary search would split at exactly 50% every time.
Count against binary search. Run a full search at Array Size 30 with Auto-Run and count the probes. Compare with the binary search module at the same size: Fibonacci search usually needs one or two more.
Find the boundary Fibonacci number. Set Array Size to 13, then 14. At 13 the array is exactly a Fibonacci number and the splits land cleanly; at 14 the algorithm pads up to 21 and the first probe sits further from the centre.
Search past the end. Set Search Target to a value larger than everything in the array. Watch the clamping keep probes inside the array even though the Fibonacci offsets would run past it — that clamp is the part implementations most often get wrong.
Where this goes wrong
Probing out of bounds.offset + F(k−2) can exceed the last index whenever n is not exactly a Fibonacci number. It must be clamped with min(offset + F(k−2), n−1), and omitting that is the classic implementation bug.
Expecting it to beat binary search. On modern hardware with a cache and a fast divider, binary search wins on almost every workload. Fibonacci search is the right choice for block-access storage or division-free processors, not as a general upgrade.
Recomputing the sequence each call. The Fibonacci numbers must be precomputed or maintained by subtraction. Regenerating them per search reintroduces the arithmetic you were avoiding.
Forgetting the sorted precondition. It is exactly as strict as binary search’s. Unsorted input gives silent wrong answers, not an error.
The short version
Fibonacci search is binary search rebuilt out of additions. It costs about 44% more comparisons because it divides by φ rather than by 2, and it earns that back only on hardware where division is expensive or where uneven, locality-friendly splits beat repeated jumps to the middle. Learn it for what it demonstrates: the halving in binary search is not sacred, and any constant-factor shrink per step still gives you a logarithm.
The related golden-section search
The Fibonacci idea has a genuinely useful relative, and it solves a different problem.
Golden-section search finds the minimum (or maximum) of a unimodal function — one that decreases then increases, with a single turning point. It cannot use binary search's comparison, because knowing a value is larger than another does not say which side the minimum is on.
Instead it evaluates the function at two interior points chosen by the golden ratio, discards the section that cannot contain the minimum, and repeats. The golden ratio is used precisely because it allows one of the two evaluation points to be reused in the next iteration, so each step costs one function evaluation rather than two.
That reuse property is the same mathematical fact that motivates Fibonacci search, applied where it actually matters — because for a continuous function each evaluation may be expensive.
Method
Finds
Requires
Binary search
A value in a sorted array
Sortedness
Fibonacci search
A value in a sorted array
Sortedness; no division
Golden-section search
The extremum of a function
Unimodality
Ternary search
The extremum of a function
Unimodality
Bisection method
A root of a function
A sign change
Ternary search does the same job as golden-section by splitting into thirds, and it needs two new evaluations per step rather than one — which is why golden-section is preferred when evaluations are costly.
Where the searching family stands
Putting the sorted-array searches together:
Binary search is the default. O(log n) guaranteed, trivial arithmetic, and the standard library implementation (bisect) is correct and fast.
Interpolation search is faster on uniformly distributed numeric data — O(log log n) — and degrades to O(n) on skewed data.
Exponential search handles unknown or unbounded array size: double the probe index until the value exceeds the target, then binary search the last interval. O(log i) where i is the target's position.
Fibonacci search matches binary search's complexity while avoiding division.
Jump search steps forward by √n and then scans linearly, giving O(√n) — worse than binary search, and it only ever moves forward, which suits sequential media.
The practical conclusion for almost all work: use bisect. The alternatives are worth knowing for the specific conditions they address — unknown size, non-uniform hardware, sequential access — and none of them beats binary search in the general case.
Practical notes
If Fibonacci search is implemented, three details cause bugs:
Index clamping.min(offset + fib2, n - 1) is necessary because the Fibonacci number may exceed the array length.
The final check. After the loop, one element may remain unexamined — the fib1 check handles it, and omitting it misses matches at the boundary.
The three-way state update. Moving the Fibonacci variables correctly on each branch is where implementations go wrong; the sequence must shift consistently.
Those are the same class of off-by-one difficulties that make binary search famously error-prone, with more state to manage — another practical argument for the simpler algorithm.
Questions people ask
Is Fibonacci search faster than binary search? No. Same complexity, marginally more comparisons, and only addition-and-subtraction arithmetic as a benefit.
Why would anyone use it? Historically, on hardware where division was expensive. Today, essentially as a curiosity.
Does it have better cache behaviour? Marginally, in theory, because its early probes are less spread out. B-trees address that problem far better.
What is golden-section search? The genuinely useful relative — it finds the extremum of a unimodal function, reusing one evaluation per step.
What should I use for a sorted array?bisect from the standard library, which is binary search done correctly.
When is exponential search better? When the array size is unknown or unbounded, or when the target is likely near the beginning.
Recap in one screen
Split the range by Fibonacci ratios (~38/62) instead of in half; complexity is still O(log n).
Its purpose was avoiding division, which mattered on hardware without a divide instruction.
Marginally more comparisons than binary search, and a small theoretical locality advantage.
Golden-section search is the useful relative: it finds a unimodal function's extremum, reusing an evaluation each step.
Use bisect for real work; the alternatives address specific conditions rather than beating it generally.
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
# Fibonacci search: divide the array at Fibonacci offsets rather than in
# half. No division, no multiplication - only + and -.
def fibonacci_search(a, target):
n = len(a)
f2, f1 = 0, 1
fib = f2 + f1
while fib < n: # smallest Fibonacci number >= n
f2, f1 = f1, fib
fib = f2 + f1
print(f"array of {n}; smallest Fibonacci number >= n is {fib}")
offset, step = -1, 0
while fib > 1:
step += 1
i = min(offset + f2, n - 1) # clamp: the array may be shorter than fib
print(f" step {step}: probe={i:>2} a[probe]={a[i]:>3} (fib={fib}, f2={f2})")
if a[i] < target:
fib, f1, f2 = f1, f2, f1 - f2 # cut off the left part
offset = i
elif a[i] > target:
fib, f1, f2 = f2, f1 - f2, f2 - (f1 - f2) # cut off the right part
else:
return i
if f1 and a[offset + 1] == target: # one candidate left
return offset + 1
return -1
data = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91, 96]
print("array:", data)
print()
for target in (72, 2, 40):
print("target", target)
print(" -> index", fibonacci_search(data, target))
print()
Output
How the code works
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.
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.
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.
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.
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.
Check yourself
0 of 3
Answer without scrolling back up.
What does Fibonacci search avoid that binary search needs?
The split points come from adding and subtracting Fibonacci numbers, so no division or bit-shift is required. On hardware without cheap division that mattered.
Its step count compared with binary search is:
Both are logarithmic and Fibonacci search is slightly worse by a constant. The win was never the step count.
Why does the probe use min(offset + f2, n - 1)?
The sequence jumps 8, 13, 21 - it rarely equals the array length, so the first probe can point past the end and has to be clamped.
Cheat sheet
Fibonacci Search
A comparison-based technique that uses Fibonacci numbers to divide the search space, avoiding costly division operators utilized in Binary or Interpolation search.
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.