What is Fibonacci Search technique?

Technology Community › Category: Divide & Conquer › What is Fibonacci Search technique?

VietMX Staff asked 3 years ago

Fibonacci search is a search algorithm based on divide and conquer principle that can find an element in the given sorted array with the help of Fibonacci series in O(log n) time complexity.

Compared to binary search where the sorted array is divided into two equal-sized parts, one of which is examined further, Fibonacci search divides the array into two unequal parts that have sizes that are consecutive Fibonacci numbers.

Some facts to note:

Fibonacci search has the advantage that one only needs addition and subtraction to calculate the indices of the accessed array elements, while classical binary search needs bit-shift, division or multiplication, operations that were less common at the time Fibonacci search was first published
Binary search works by dividing the seek area in equal parts 1:1. Fibonacci search can divide it into parts approaching 1:1.618 while using the simpler operations.
On average, Fibonacci search requires 4% more comparisons than binary search
Fibonacci Search examines relatively closer elements in subsequent steps. So when input array is big that cannot fit in CPU cache or even in RAM, Fibonacci Search can be useful. Thus Fibonacci search may have the advantage over binary search in slightly reducing the average time needed to access a non-uniform access memory storage.

Let the length of given array be length and the element to be searched be key.

Steps of Fibonacci Search:

Find the smallest Fibonacci number F(n) that F(n) - 1 >= length

F(n) = F(n-1) + F(n-2) => F(n) - 1 = [ F(n-1) - 1 ] + (1) + [ F(n-2) - 1 ], where (1) here is for the middle item (the m in below figure).

// |<---------             p: F(n) - 1             --------->|
// |<---    q: F(n-1) - 1    --->|   |<--  r: F(n-2) - 1  -->|
// +----+---+--------------------+---+---+---+---+
// |    | k |                    | m |   | k |   |
// +----+---+--------------------+---+---+---+---+
//                                 ^

If key < m, then search key in q = F(n-1) - 1:
```
// |<---    p: F(n-1) - 1    --->|
// |<----- q ----->|   |<-- r -->|
// +----+---+------+---+---------+
// |    | k |      | m |         |
// +----+---+------+---+---------+
```
for that set p = F(n-1) - 1, q = F(n-2) - 1, r = F(n-3) - 1 and repeat the process. Here Fibonacci numbers go backward once. These indicate elimination of approximately one-third of the remaining array.
If key > m, then repeat then search key in r = F(n-2) - 1:
```
// |<--  p: F(n-2) - 1  -->|
// |<--- q --->|   |<- r ->|
// +---+---+---+
// |   | k |   | m
// +---+---+---+
//               ^
```
For that, set p = F(n-2) - 1, q = F(n-3) - 1, r = F(n-4) - 1 and repeat the process. Here Fibonacci numbers go backward twice, indicating elimination of approximately two-third of the remaining array.

Complexity Analysis

Fibonacci search has an average- and worst-case complexity of O(log n). The worst case will occur when we have our target in the larger (2/3) fraction of the array, as we proceed to find it. In other words, we are eliminating the smaller (1/3) fraction of the array every time. We call once for n, then for (2/3) n, then for (4/9) n and henceforth.

Implementation

#include <algorithm>
#include <cassert>
#include "search.h"

typedef struct FibonacciValues
{
  // Fibonacci number: F(n) = F(n-1) + F(n-2)
  int Fn_2; // F(n-2)
  int Fn_1; // F(n-1)
  int Fn;   // F(n)

  FibonacciValues(int fn_2, int fn_1, int fn)
    : Fn_2(fn_2)
    , Fn_1(fn_1)
    , Fn(fn)
  {
    assert(Fn == Fn_1 + Fn_2);
  }

  ~FibonacciValues()
  {
  }

  void forward()
  {
    Fn_2 = Fn_1;
    Fn_1 = Fn;
    Fn = Fn_1 + Fn_2;
    assert(Fn == Fn_1 + Fn_2);
  }

  void backward()
  {
    Fn = Fn_1;
    Fn_1 = Fn_2;
    Fn_2 = Fn - Fn_1;
    assert(Fn == Fn_1 + Fn_2);
  }

} FibonacciValues;

// Returns the smallest Fibonacci number that is greater than or equal to k.
FibonacciValues GetFibonacci(int k)
{
  FibonacciValues fib(0, 1, 1);
  while (fib.Fn < k) {
    fib.forward();
  }
  return fib;
}

// Notice that the current middle might exceed the array!

int fibonacciSearch(int list[], const unsigned int length, int key)
{
  assert(list && length);

  int left = 0, right = length - 1, middle;
  // Find a fibonacci number F(n) that F(n) - 1 >= length
  FibonacciValues fib = GetFibonacci(length + 1);

  while (left <= right) {
    // Avoid the middle is over the array.
    middle = std::min(left + (fib.Fn_1 - 1), right);

    if (list[middle] == key) {
      return middle;
    } else if (list[middle] > key) {
      right = middle - 1;
      fib.backward();
    } else { // list[middle] < key
      left = middle + 1;
      fib.backward(); fib.backward();
    }
  }

  return NOT_FOUND;
}

Question Tags: Divide & Conquer, Junior Level