1. Fibonacci state
Track consecutive Fibonacci numbers.
let fib2 = 0Typorithm · hard
Fibonacci Search
▷ Interactive algorithm labfibonacci-searchsearchsorted-arrayfibonaccilogarithmic-time
Saved on this device
Full lesson · 8 learning steps Open any exercise for focused practice
10%
Step 1 of 8 · intro card
Learn Fibonacci Search
Search Algorithms
Fibonacci Search narrows a sorted array using Fibonacci-sized probe positions.
Fibonacci Search is another sorted-array search strategy.
It first finds a Fibonacci number large enough to cover the array.
The offset marks the part already eliminated from the left.
Each comparison shrinks the Fibonacci window.
It is logarithmic and historically useful where division was expensive.
Preparing algorithm lab…
01
Requires sorted input.
02
Use Fibonacci window sizes.
03
Track eliminated left side with offset.
04
Probe at offset + fib2.
05
Time is O(log n).
function fibonacciSearch(arr, target) {
let fib2 = 0;
let fib1 = 1;
let fib = fib1 + fib2;
while (fib < arr.length) {
fib2 = fib1;
fib1 = fib;
fib = fib1 + fib2;
}
let offset = -1;
while (fib > 1) {
const i = Math.min(offset + fib2, arr.length - 1);
if (arr[i] < target) {
fib = fib1;
fib1 = fib2;
fib2 = fib - fib1;
offset = i;
} else if (arr[i] > target) {
fib = fib2;
fib1 = fib1 - fib2;
fib2 = fib - fib1;
} else {
return i;
}
}
if (fib1 && arr[offset + 1] === target) return offset + 1;
return -1;
}Read the implementation
Connect each part of the code to the concept before you type.
2. Grow range
Find the smallest Fibonacci number covering the array length.
while (fib < arr.length)3. Offset
offset marks the eliminated left side.
let offset = -14. Probe index
Probe using a Fibonacci-sized step from the offset.
const i = Math.min(offset + fib2, arr.length - 1)5. Move right
If the probe is too small, eliminate everything through i.
offset = i6. Return hit
Return the probe index on a match.
return i7. Last check
Check the final remaining candidate.
if (fib1 && arr[offset + 1] === target) return offset + 1A complete learning loop
01
Understand
Read the concept map and follow the code breakdown.
02
Reconstruct
Type the implementation, repair mistakes and work through every recall exercise.
03
Verify
Use the final check without hints; revisit weak concepts in short practice sessions.