Binary Search
Efficiently finds a target value by halving the search space each step.
Searches a sorted array using Fibonacci numbers to narrow the range.
Fibonacci Search is a comparison-based algorithm for finding a target element in a sorted array. Instead of dividing the search space exactly in half as Binary Search does, it uses consecutive Fibonacci numbers to determine where to split the array, producing unequal partitions that shrink according to the Fibonacci sequence. The algorithm was first described by Jack Kiefer in 1953 in the context of optimization and later adapted for search problems. It represents a fascinating intersection of number theory and algorithm design, demonstrating how the mathematical properties of the Fibonacci sequence can be applied to practical computing problems.
The Fibonacci sequence, where each number is the sum of the two preceding ones (1, 1, 2, 3, 5, 8, 13, 21, ...), was described by Leonardo of Pisa in 1202, though it appeared in Indian mathematics centuries earlier. The key property that makes it useful for searching is that each Fibonacci number can be computed from the two before it using only addition, and the ratio between consecutive Fibonacci numbers approaches the golden ratio (approximately 1.618). This means the search space shrinks by a factor related to the golden ratio at each step rather than exactly by half.
offset + F(k-2), which divides the current Fibonacci-length range into two sub-ranges whose lengths are themselves consecutive Fibonacci numbers.
The elegance of this approach is that all index calculations use only addition and subtraction, never division. The Fibonacci numbers serve as precomputed split points that naturally decompose the search space into smaller Fibonacci-sized segments.
| Case | Time | Space |
|---|---|---|
| Best | O(1) | O(1) |
| Average | O(log n) | O(1) |
| Worst | O(log n) | O(1) |
The time complexity is O(log n) because the Fibonacci numbers grow exponentially (at a rate of the golden ratio per step), so the search space shrinks by a constant factor at each comparison, just as in Binary Search. More precisely, Fibonacci Search makes about 4% more comparisons on average than Binary Search because the golden ratio base logarithm is slightly larger than the base-2 logarithm.
Fibonacci Search was developed during an era when division was an expensive operation on many processors. Since the algorithm computes split points using only addition and subtraction of precomputed Fibonacci numbers, it avoided the costly division required by Binary Search's midpoint calculation. On early hardware where division could take many more clock cycles than addition, this was a meaningful practical advantage.
Another historical advantage relates to memory access patterns on sequential storage media such as magnetic tape. Binary Search always jumps to the exact middle of the remaining range, which can mean large jumps on tape. Fibonacci Search's unequal partitioning tends to produce one smaller and one larger sub-range, and if the target falls in the larger sub-range, the subsequent access is closer to the previous position. This locality property made Fibonacci Search more efficient for tape-based storage systems where seek time was proportional to distance traveled.
On modern hardware with fast division and random-access memory, Binary Search is almost always preferred over Fibonacci Search. Modern processors execute division in a single clock cycle, eliminating the arithmetic advantage. RAM provides constant-time access regardless of address distance, eliminating the locality advantage. Binary Search is also simpler to implement and understand, has a smaller constant factor, and is available in standard libraries of every major programming language.
Fibonacci Search is primarily of theoretical and educational interest today. It demonstrates how mathematical sequences can be leveraged in algorithm design and how hardware characteristics can influence algorithm choice. It remains relevant in niche scenarios involving non-uniform access costs, embedded systems with limited arithmetic capabilities, or as a teaching tool for understanding search algorithm trade-offs beyond the standard Binary Search approach.