Must the array length be a Fibonacci number?

No. The algorithm can start with a covering Fibonacci size and handle the actual array boundary explicitly.

Does it search only numerical data?

No. Any consistently ordered values can be compared, provided the implementation supports their comparison and access requirements.

Is it the same as Fibonacci optimization?

No. This entry finds a target in sorted data. The optimization use concerns locating an optimum under different assumptions.

AI Glossary / Graphs and symbolic AI / Intermediate

Fibonacci search technique

Definition

The Fibonacci search technique locates a value in a sorted array by using Fibonacci numbers to choose successive comparison positions. Each comparison discards an impossible part of the remaining interval. It resembles binary search, but uses a sequence of unequal partitions based on Fibonacci numbers rather than repeatedly taking the midpoint.

What it means

The Fibonacci sequence begins 0, 1, 1, 2, 3, 5, 8, 13 and continues by adding the preceding two numbers. The same relationship lets a search move between progressively smaller interval sizes using addition and subtraction.

This entry concerns searching ordered records for a target value. A different method also called Fibonacci search is used in one-dimensional optimization of a unimodal function. Keep these uses distinct. Neither technique implies that the data itself must contain Fibonacci numbers: the sequence controls where the algorithm looks, not the values being searched.

How it works

An array-search implementation begins with Fibonacci numbers large enough to cover the array length. It maintains a boundary for the part already excluded and chooses a candidate position using a smaller Fibonacci offset. A bound check ensures that the candidate stays within the finite array.

If the candidate equals the target, the search succeeds. If it is smaller, the search discards the earlier portion and updates its offset and Fibonacci sizes. If it is larger, the search retains an earlier portion and reduces the sizes differently. Eventually it finds the target or establishes that no matching position remains, including any required final single-position check.

Because Fibonacci numbers grow geometrically, the number of comparison stages is O(log n) for n elements under the usual indexed-access assumptions. The search does not include the cost of initially sorting the data. Exact index formulas depend on the chosen convention, so mixing formulas from different variants can cause boundary errors.

Three practical examples

1. A programmer searches a sorted numeric table with Fibonacci-guided probes as an alternative comparison-based lookup method. The table may contain ordinary identifiers rather than Fibonacci values.

2. An algorithms course compares its probe sequence with binary search on the same array. Students can see that both discard ordered intervals even though their split positions differ.

3. An embedded-software experiment evaluates an implementation whose probe updates use addition and subtraction. Any practical advantage must be measured on the actual hardware and workload, not inferred solely from the algorithm's historical motivation.

Think of it this way

Think of looking through an ordered filing cabinet using a prepared set of progressively smaller stepping distances. Each comparison tells you which portion cannot contain the file, and the remaining stepping distances adapt accordingly. The analogy explains narrowing an interval. It does not imply that physically walking between drawers costs the same as direct array access or that the chosen steps always minimize elapsed time.

Worked example

Use zero-based positions in the sorted array [3, 7, 11, 15, 19, 23, 27, 31, 35, 39], and search for 35. Consider the common offset variant that starts with Fibonacci triple (13, 8, 5), covering length ten, and an excluded-prefix offset of −1. Its probe is the smaller of offset plus the third number and the last valid index.

First probe index −1 + 5 = 4, containing 19. Since 35 is larger, set the offset to 4 and reduce the triple to (8, 5, 3). Probe index 4 + 3 = 7, containing 31. Again the target is larger: offset becomes 7 and the triple becomes (5, 3, 2).

Probe index 7 + 2 = 9, containing 39. The target is smaller, so retain offset 7 and reduce the triple to (2, 1, 1). The next probe is index 8, containing 35, so the search succeeds. This four-comparison hand trace illustrates one implementation convention; it is not a performance benchmark or the only valid Fibonacci-search variant.

Illustrative case study

Fictional case study: Alder Tables tests a Fibonacci-search routine for sorted identifiers. Initial examples pass, but a review asks what happens when the target is absent, lies below the first value or exceeds the last value. The team also tests lengths that are not Fibonacci numbers.

It finds that the algorithm must cap probe indices and preserve a final candidate correctly. The revised evaluation compares results against a straightforward trusted lookup before measuring speed. The case illustrates boundary testing, without claiming that this technique outperformed the team's existing search method.

Common misconceptions and mistakes

The array must be ordered consistently with the comparison operation. Sorting by one rule and searching by another invalidates the interval exclusions. Values do not need a uniform numerical distribution; the method uses order, not a statistical guess about where a value should fall.

Fibonacci search is not automatically faster than binary search. Instruction costs, memory access and implementation overhead all matter. Also, finding any matching duplicate differs from finding the first or last match. That requirement needs explicit handling, rather than assuming an equality hit has already answered every version of the lookup question.

Business use

For business software, this is usually an implementation-level choice beneath an exact lookup feature. The requirements are correct results, defined missing-value behavior and dependable performance on representative data. A familiar library routine may be preferable unless there is evidence supporting a specialized implementation.

Document the indexing convention and comparator, then test empty inputs, short arrays, extreme targets and duplicate keys. Measure complete operation costs, including data preparation where relevant. Keep the distinction between comparison complexity and runtime visible: a logarithmic comparison bound does not make remote or sequential storage behave like a random-access array.

Check your understanding

Why does the worked search retain its offset after comparing 35 with the value 39 at index 9?

Answer: It must search earlier than index 9 while preserving the already excluded prefix through index 7. Changing the Fibonacci sizes moves the next probe to index 8.

Related terms

Binary search
sorted array
Fibonacci number
comparison-based search
random access
search interval
boundary condition
algorithmic complexity

Learn next

Trace present and absent targets using one documented variant. Compare its surviving interval with binary search at each step, then test non-Fibonacci lengths and duplicate-handling requirements before considering optimization.

Binary search

Sources

Primary references: NIST, “Fibonaccian search”: https://xlinux.nist.gov/dads/HTML/fibonaccianSearch.html ; The Algorithms, Python implementation: https://raw.githubusercontent.com/TheAlgorithms/Python/master/searches/fibonacci_search.py . The numerical trace uses an explicitly stated offset convention and is original teaching material; no hardware-speed claim is made.

Previous: Fibonacci coding Next: Field experiment