Fibonacci Search

Fibonacci search is a comparison-based technique that uses Fibonacci numbers to search an element in a sorted array. It divides the array into unequal parts, using only addition and subtraction to calculate split points—making it potentially faster than binary search on some architectures.

Target Value

Speed (ms)

idx 0

idx 1

idx 2

idx 3

idx 4

idx 5

idx 6

idx 7

idx 8

idx 9

100

idx 10

235

idx 11

fibM0

fibM-10

fibM-20

Offset-1

Understanding Fibonacci Search

Fibonacci Search is a divide-and-conquer algorithm designed for sorted arrays. Unlike Binary Search, which always divides the segment in half, Fibonacci search uses Fibonacci numbers to divide the range into two parts of unequal lengths.

Why "unequal" splits?

While binary search requires division (often bitwise shift) to find the midpoint, Fibonacci search relies only on addition and subtraction. Historically, this made it efficient on hardware where division operations were significantly slower than addition.

Key Features

Works on sorted arrays only
Maintains O(log n) time complexity
Uses addition/subtraction instead of division
Divides search space into fib(m-1) and fib(m-2) segments

Comparison with Binary Search

Binary Search splits 50/50; Fibonacci splits ~61/38.
Fibonacci search may reduce memory access overhead in systems with distinct caching layers.

Algorithm Specs

Best CaseO(1)

Average/Worst CaseO(log n)

Space ComplexityO(1)

Search Process

Start the search to see log...

Formula

F(m) = F(m-1) + F(m-2)
split = min(offset + F(m-2), n-1)

* offset represents the eliminated range from the left.

Recursive Implementation

Here is the standard iterative implementation of Fibonacci Search. It first finds the smallest Fibonacci number strictly greater than or equal to the array length, and then proceeds with splits.

Pseudocode

Python

1def fibonacci_search(arr, x):
2    n = len(arr)
3    # Initialize fibonacci numbers
4    fibSumM2 = 0 
5    fibSumM1 = 1 
6    fibSum = fibSumM2 + fibSumM1 
7 
8    while (fibSum < n):
9        fibSumM2 = fibSumM1
10        fibSumM1 = fibSum
11        fibSum = fibSumM2 + fibSumM1
12 
13    offset = -1
14 
15    while (fibSum > 1):
16        i = min(offset + fibSumM2, n-1)
17 
18        if (arr[i] < x):
19            fibSum = fibSumM1
20            fibSumM1 = fibSumM2
21            fibSumM2 = fibSum - fibSumM1
22            offset = i
23        elif (arr[i] > x):
24            fibSum = fibSumM2
25            fibSumM1 = fibSumM1 - fibSumM2
26            fibSumM2 = fibSum - fibSumM1
27        else:
28            return i
29 
30    if(fibSumM1 and arr[offset+1] == x):
31        return offset+1
32 
33    return -1

JavaScript Implementation:

Pseudocode

JavaScript

1function fibonacciSearch(arr, x) {
2  let n = arr.length;
3  let fibMM2 = 0; // (m-2)'th Fibonacci No.
4  let fibMM1 = 1; // (m-1)'th Fibonacci No.
5  let fibM = fibMM2 + fibMM1; // m'th Fibonacci
6 
7  while (fibM < n) {
8    fibMM2 = fibMM1;
9    fibMM1 = fibM;
10    fibM = fibMM2 + fibMM1;
11  }
12 
13  let offset = -1;
14 
15  while (fibM > 1) {
16    let i = Math.min(offset + fibMM2, n - 1);
17 
18    if (arr[i] < x) {
19      fibM = fibMM1;
20      fibMM1 = fibMM2;
21      fibMM2 = fibM - fibMM1;
22      offset = i;
23    } else if (arr[i] > x) {
24      fibM = fibMM2;
25      fibMM1 = fibMM1 - fibMM2;
26      fibMM2 = fibM - fibMM1;
27    } else return i;
28  }
29 
30  if (fibMM1 && arr[offset + 1] === x) return offset + 1;
31 
32  return -1;
33}

Understanding Fibonacci Search

Why "unequal" splits?

Recursive Implementation

Here is the standard iterative implementation of Fibonacci Search. It first finds the smallest Fibonacci number strictly greater than or equal to the array length, and then proceeds with splits.

Pseudocode

Python

1def fibonacci_search(arr, x):
2    n = len(arr)
3    # Initialize fibonacci numbers
4    fibSumM2 = 0 
5    fibSumM1 = 1 
6    fibSum = fibSumM2 + fibSumM1 
7 
8    while (fibSum < n):
9        fibSumM2 = fibSumM1
10        fibSumM1 = fibSum
11        fibSum = fibSumM2 + fibSumM1
12 
13    offset = -1
14 
15    while (fibSum > 1):
16        i = min(offset + fibSumM2, n-1)
17 
18        if (arr[i] < x):
19            fibSum = fibSumM1
20            fibSumM1 = fibSumM2
21            fibSumM2 = fibSum - fibSumM1
22            offset = i
23        elif (arr[i] > x):
24            fibSum = fibSumM2
25            fibSumM1 = fibSumM1 - fibSumM2
26            fibSumM2 = fibSum - fibSumM1
27        else:
28            return i
29 
30    if(fibSumM1 and arr[offset+1] == x):
31        return offset+1
32 
33    return -1

JavaScript Implementation:

Pseudocode

JavaScript

1function fibonacciSearch(arr, x) {
2  let n = arr.length;
3  let fibMM2 = 0; // (m-2)'th Fibonacci No.
4  let fibMM1 = 1; // (m-1)'th Fibonacci No.
5  let fibM = fibMM2 + fibMM1; // m'th Fibonacci
6 
7  while (fibM < n) {
8    fibMM2 = fibMM1;
9    fibMM1 = fibM;
10    fibM = fibMM2 + fibMM1;
11  }
12 
13  let offset = -1;
14 
15  while (fibM > 1) {
16    let i = Math.min(offset + fibMM2, n - 1);
17 
18    if (arr[i] < x) {
19      fibM = fibMM1;
20      fibMM1 = fibMM2;
21      fibMM2 = fibM - fibMM1;
22      offset = i;
23    } else if (arr[i] > x) {
24      fibM = fibMM2;
25      fibMM1 = fibMM1 - fibMM2;
26      fibMM2 = fibM - fibMM1;
27    } else return i;
28  }
29 
30  if (fibMM1 && arr[offset + 1] === x) return offset + 1;
31 
32  return -1;
33}