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)
Deconstructing Fibonacci Search
A clever search algorithm that uses nature's favorite number sequence to find elements without multiplication or division.
Quick Context: What is Fibonacci Search?
Fibonacci Search is a "divide and conquer" algorithm that finds an element in a sorted array. Unlike Binary Search, which splits the array in half, Fibonacci Search splits it into two unequal parts based on Fibonacci numbers. Its main advantage is that it only uses addition and subtraction to calculate probe positions, making it faster than Binary Search on systems where division operations are slow.
The Core Idea: Golden Ratio Partitioning
The Fibonacci sequence (0, 1, 1, 2, 3, 5, 8, ...) has a property where the ratio of two consecutive numbers approaches the Golden Ratio (~1.618). The algorithm leverages this to narrow down the search space.
Find the Right Fibonacci Number: First, we find the smallest Fibonacci number, let's call it `fibM`, that is greater than or equal to the array size `n`.
Set the Probes: The algorithm maintains three Fibonacci numbers: `fibM` (`fib(m)`), `fibM_1` (`fib(m-1)`), and `fibM_2` (`fib(m-2)`). The first probe position is calculated as `offset + fibM_2`. The `offset` is initially -1.
Compare and Discard:
If the target is at the probe position, we're done!
If the target is less than the probe element, we discard the right part of the array. The new search space has a size of `fibM_2`, and we update our Fibonacci numbers by moving down the sequence twice (`m = m - 2`).
If the target is greater than the probe element, we discard the left part. The new search space has a size of `fibM_1`. We update the `offset` to the probe position and move down the sequence once (`m = m - 1`).
Guided Experiments with the Visualizer
Initial State: The visualizer shows a sorted array. The "Fibonacci State" panel displays the initial `fibM`, `fibM_1`, and `fibM_2` values calculated for the array size.
First Step: Click "Next Step". A "Probe" pointer appears at an index calculated using `fibM_2`. This is our first comparison point. The bar at this index is highlighted in yellow.
Target is Greater: Let's assume your target value (e.g., 42) is greater than the value at the probe index. Click "Next Step" again. The entire left portion of the array (including the probe) is marked as "discarded" (faded out). The `offset` pointer moves to the probe's location, and the Fibonacci numbers in the state panel are updated (`m` becomes `m-1`).
Target is Smaller: Now, reset and set a target that is smaller than the first probe. Click "Next Step". This time, the right portion of the array is discarded. The `offset` doesn't move, but the Fibonacci numbers are updated differently (`m` becomes `m-2`).
Auto-Run to Finish: Set a target and click "Auto-Run". Watch how the algorithm repeatedly shrinks the search space using Fibonacci numbers until the "Probe" lands on the target, turning the bar green.
Comparison with Binary Search
Division vs. Addition/Subtraction: Fibonacci Search avoids division, which can be a performance win on certain hardware.
Probe Location: Binary Search always probes the exact middle. Fibonacci Search probes at points that are not central, which can sometimes be more efficient for data stored in slow-access memory (like tape drives), as the next probe is more likely to be close to the current one.
Complexity: Both algorithms have a time complexity of O(log n), making them very efficient for large datasets.
Key Takeaways
Requires Sorted Array: Just like Binary Search, the data must be sorted for Fibonacci Search to work.
Uneven Splitting: The core mechanism is splitting the array into uneven chunks whose sizes are consecutive Fibonacci numbers.
Arithmetic Simplicity: Its main strength is replacing costly division/multiplication with simple addition and subtraction.
Logarithmic Performance: It's an extremely fast search algorithm for large arrays, with performance comparable to Binary Search.
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.