Fibonacci Search Visualizer

Target:

Speed:

SlowFast

Elements:

715

(10)

Probe

Boundaries

Target Value

Found

Other

Operation Logs

No operations yet

Algorithm Info

Time Complexity: O(log n)

Space Complexity: O(1) - uses constant extra space

Best Case: O(1) - target is at probe position

Worst Case: O(log n)

Prerequisite: Array must be sorted in ascending order

How it works: Uses Fibonacci numbers to divide the array and probe for the target. Shrinks the search space using the sequence.

Advantage: Useful for large sorted arrays with slow access times.

When to use: When array is sorted and random access is expensive.

Implementation

function fibonacciSearch(arr, target) {
  let n = arr.length;
  let fibMm2 = 0, fibMm1 = 1, fibM = fibMm2 + fibMm1;
  while (fibM < n) {
    fibMm2 = fibMm1;
    fibMm1 = fibM;
    fibM = fibMm2 + fibMm1;
  }
  let offset = -1;
  while (fibM > 1) {
    let i = Math.min(offset + fibMm2, n - 1);
    if (arr[i] < target) {
      fibM = fibMm1;
      fibMm1 = fibMm2;
      fibMm2 = fibM - fibMm1;
      offset = i;
    } else if (arr[i] > target) {
      fibM = fibMm2;
      fibMm1 = fibMm1 - fibMm2;
      fibMm2 = fibM - fibMm1;
    } else {
      return i;
    }
  }
  if (fibMm1 && arr[offset + 1] === target) return offset + 1;
  return -1;
}