[1] Compared to binary search where the sorted array is divided into two equal-sized parts, one of which is examined further, Fibonacci search divides the array into two parts that have sizes that are consecutive Fibonacci numbers.
On average, this leads to about 4% more comparisons to be executed,[2] but it has the advantage that one only needs addition and subtraction to calculate the indices of the accessed array elements, while classical binary search needs bit-shift (see Bitwise operation), division or multiplication,[1] operations that were less common at the time Fibonacci search was first published.
If the data is stored on a magnetic tape where seek time depends on the current head position, a tradeoff between longer seek time and more comparisons may lead to a search algorithm that is skewed similarly to Fibonacci search.
To test whether an item is in the list of ordered numbers, follow these steps: Alternative implementation (from "Sorting and Searching" by Knuth[4]): Given a table of records R1, R2, ..., RN whose keys are in increasing order K1 < K2 < ... < KN, the algorithm searches for a given argument K. Assume N+1= Fk+1 Step 1.
Otherwise set (i, p, q) ← (i + q, p − q, 2q − p) (which moves p and q two positions back in the Fibonacci sequence); and return to Step 2 The two variants of the algorithm presented above always divide the current interval into a larger and a smaller subinterval.