Overview
Fibonacci Search narrows a sorted array with offsets based on Fibonacci numbers instead of midpoint division.
CoreSource checked
Fibonacci Search
Searches sorted data using Fibonacci-sized partitions.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Searching
- Difficulty
- Intermediate
- Family
- Divide and Conquer
- Tier
- Core
- Status
- Verified
- Review
- Source Checked
- Sources
- 1
- Formulas
- 0
- Relationships
- 1
- Code example
- Ready
- Visualization
- Ready
Core Concepts
candidate searchsorted search spacedivide and conquercandidate spacematch testsearch interval
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(1)
Average
O(log n)
Worst
O(log n)
Space
O(1)
When to Use
- Use Fibonacci Search when you need to partition a sorted array with Fibonacci offsets.
- Use it when the input assumptions match the method's model.
- Use it when you need a clear lookup strategy for known input organization.
- Use it when the method's tradeoffs fit the workload.
When Not to Use
- Avoid it when the input cannot be kept sorted cheaply.
- Avoid it when maintaining the required data layout costs more than the lookup saves.
- Avoid it when the required output is not index of target.
What It Does
- Partitions a sorted array with Fibonacci offsets
- Narrows the candidate range after each comparison
Use Cases
- Searching sorted arrays
- Systems where sequential access is cheaper
- Teaching alternative logarithmic search
Inputs
- Sorted array
- Target value
Outputs
- Index of target
- Not-found result
Pseudocode
- 1.Find the smallest Fibonacci number at least as large as the input
- 2.Compare at the current Fibonacci offset
- 3.Drop the lower or upper range
- 4.Move down the Fibonacci sequence
- 5.Return the matching index or not found
Canonical Example
- Input
- values = [2, 5, 8, 12, 16], target = 12
- Output
- index = 3
- Explanation
- Fibonacci Search: The search checks candidate positions until it identifies the target value.
Implementation Notes
- Keep the input contract explicit: Sorted array; Target value.
- Decide up front whether not-found results return null, -1, false, or an insertion position.
- Search algorithms should define both success and failure semantics.
Common Pitfalls
- Binary Search is usually simpler, but Fibonacci Search is a useful comparison point.
- Handle empty, invalid, and boundary inputs before trusting index of target.
- Off-by-one bounds, duplicates, and missing-target behavior should be specified before implementation.
Interactive Mechanism Walkthrough
Indexed Interval & Boundary ProbeShow partitions sized by Fibonacci numbers shrinking the search range.
Target key: 41low=0, mid=4, high=9
4[0]
9[1]
15[2]
22[3]
27[4]
34[5]
41[6]
49[7]
58[8]
63[9]
Step 1 of 5: Find the smallest Fibonacci number at least as large as the input
fibonacci-partitionsNotes
Fibonacci Search operates in O(log n) time and O(1) space within the Divide and Conquer family. Often compared with Binary Search and Exponential Search.
Sources (1)
What each reference supports for this entry.
The Art of Computer Programming, Volume 3
BookSorting and searching reference supporting Fibonacci Search probe strategy, comparison structure, or implementation invariant.
Explore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Relationships
View full relationship pageAlternative toBinary Search
Fibonacci search is an ordered-array search alternative that uses Fibonacci offsets instead of halving.
Related Algorithms
Tags
SearchSorted DataClassic