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.