Fibonacci search
Fibonacci search finds the smallest Fibonacci number at least as large as the array, then uses the two Fibonacci numbers below it to split off a block from the front of the remaining range, comparing the value at that split point with the target and shrinking to a smaller consecutive pair of Fibonacci numbers depending on the result. It narrows the range the way binary search does, but by adding and subtracting Fibonacci numbers rather than dividing a midpoint in half.
When it is the right choice
Fibonacci search exists for machines where division is markedly more expensive than addition and subtraction — true of some early processors, not of anything in general use today. On modern hardware, integer division by two is as cheap as any other arithmetic operation, so binary search is simply the better choice: the same O(log n) bound, no Fibonacci bookkeeping, and a simpler halving rule. It is kept here for what it demonstrates: an algorithm whose entire reason to exist was a hardware constraint that no longer holds.
How it works
- Find the smallest Fibonacci number that is at least as large as the array length.
- Use the two Fibonacci numbers immediately below it to choose a split point: the front block spans the smaller of the two.
- Compare the value at the split point with the target.
- If the target is larger, drop the front block and shrink to the next-smaller consecutive pair of Fibonacci numbers.
- If the target is smaller, keep only the front block and shrink to the pair of Fibonacci numbers below that.
- If a single position is ever left over at the end, check it directly with one last comparison, by addition rather than another halving.
Worth noticing
- Every step here uses only addition and subtraction to pick the next split point — no division and no multiplication — which was the entire reason to use it on hardware where division was slow. That hardware is not what this runs on, so treat it as the history lesson it is, not a technique to reach for.
- It reaches the same O(log n) bound as binary search by the same halving-like narrowing, just anchored to Fibonacci numbers instead of a computed midpoint.
Cost
- Best
- O(1)
- Average
- O(log n)
- Worst
- O(log n)
- Extra space
- O(1)