Fibonacci Search algorithm

search
algorithm
fibonacci-search

(Team) #1

Fibonacci Search

Fibonacci search technique is a method of searching a sorted array using a divide and conquer algorithm that narrows down possible locations with the aid of Fibonacci numbers. 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 parts that have sizes that are consecutive Fibonacci numbers.

Implementation in various languages: here

You can contribute too!

Complexity Notation
Worst case time complexity O(log n)
Average case time complexity O(log n)
Best case time complexity O(1)
Average space complexity O(1)

Algorithm

Given a table of records R1, R2, …, RN whose keys are in increasing order K1 < K2 < … < KN, the algorithm searches for a given argument K. Assume N+1 = Fk+1

  • Step 1. [Initialize] i ← Fk, p ← Fk-1, q ← Fk-2 (throughout the algorithm, p and q will be consecutive Fibonacci numbers)

  • Step 2. [Compare] If K < Ki, go to Step 3; if K > Ki go to Step 4; and if K = Ki, the algorithm terminates successfully.

  • Step 3. [Decrease i] If q=0, the algorithm terminates unsuccessfully. Otherwise set (i, p, q) ← (p, q, p - q) (which moves p and q one position back in the Fibonacci sequence); then return to Step 2

  • Step 4. [Increase i] If p=1, the algorithm terminates unsuccessfully. Otherwise set (i,p,q) ← (i + q, p - q, 2q - p) (which moves p and q two positions back in the Fibonacci sequence); and return to Step 2

Continue the discussion in the comments.