Fibonacci search

O(log n)

Fibonacci search is like binary search but splits the range at offsets given by Fibonacci numbers instead of the midpoint. It only ever adds or subtracts (no division), which made it attractive on early hardware, and it touches array positions that tend to be close together (cache-friendly). It runs in O(log n) on a sorted array.

Array
Edit the input and press Play

How it works

  1. Find the smallest Fibonacci number ≥ the array length.
  2. Probe at an offset given by a smaller Fibonacci number.
  3. If the value is smaller, move the Fibonacci window down and advance the offset.
  4. If larger, shrink the window further; repeat until found or exhausted.

Pseudocode

1fibonacciSearch(a, target):         # O(log n) — a is sorted2  grow Fibonacci numbers until fib ≥ n3  offset ← -14  while fib > 1:5    i ← min(offset + fib₋₂, n-1)6    if a[i] < target: shift fibs down; offset ← i7    else if a[i] > target: shift fibs down twice8    else: return i9  return (a[offset+1] = target) ? offset+1 : -1