DSAverse
Searching Algorithms
Loading Searching Algorithms...
Search Visualization
3
9
14
21
28
35
47
56
63
72
sorted arrayindex 0
Initializing Sorting Algorithms...
Sorting
Trees
Graphs
Preparing interactive visualizations...
Searching Algorithms
Loading Searching Algorithms...
Search Visualization
A sorted-array search that uses Fibonacci numbers and only addition — no division required.
Fibonacci sequence: 0, 1, 1, 2, 3, 5, 8, 13, 21, ...
Press Play to start the visualization.
Fibonacci search uses Fibonacci numbers to divide the array into unequal parts. The key insight is that the probe index is computed as offset + fibM2, using only addition — no division needed.
After each comparison, the Fibonacci triple (fibM2, fibM1, fibM) is updated by shifting: move left or right depending on whether the target is smaller or larger.
Each step eliminates roughly 38% or 62% of the remaining range (vs 50% for binary search), due to the golden ratio properties of Fibonacci numbers.
What is the key advantage of Fibonacci search over binary search in terms of operations used?