A Fibonaccian search is an O(ln(n)) searching algorithm which attempts to improve on a binary search by making a more appropriate choice of entry to test. The choice of entries searched is based on the Fibonacci sequence where an entry is equal to the sum of the two previous values in the sequence. As the numbers in the sequence become large, the ratio between two consecutive numbers appraoches φ = (√5 + 1)/2, the golden ratio.

If the appropriate interval can be chose (based on distance from obj), then the number of iterations can be reduced to log_φ(n)/2.

The basic implementation does exactly this using a recursive algorithm.

The enhanced array-based implementation:

• Uses an iterative form of the implementation,
• Calls a linear search algorithm if the interval being searched is of width 18 or less—the overhead of recalculating the centre multiple times is greater than just walking through the eighteen entries using a linear search,
• Has a front end which checks if the entry being searched for is outside the bounds of the array.

The enhanced pointer-based implementation uses the same enhancements used with the binary search algorithm.