Fibonacci search techniqueis a method of searching a sorted array using a divide and conquer algorithm that narrows down possible locations with the aid of Fibonacci numbers.
Fibonacci search is derived from Golden section search, an algorithm by Jack Kiefer (1953) to search for the maximum or minimum of a unimodal function in an interval. 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
Fibonacci search has an average- and worst-case complexity of O(log n) (see Big O notation).
Example :
Following are the implementation of Fibonacci search into programs
// C program for Fibonacci Search
#include
// Utility function to find minimum of two elements
int min (int x, int y) {return (x <= y)? x : y; }
/* Returns index of x if present, else returns -1 */
int fibMonaccianSearch(int arr[], int x, int n)
{
/* Initialize fibonacci numbers */
int fibMMm2 = 0; // (m-2)'th Fibonacci No.
int fibMMm1 = 1; // (m-1)'th Fibonacci No.
int fibM = fibMMm2 + fibMMm1; // m'th Fibonacci
/* fibM is going to store the smallest Fibonacci
Number greater than or equal to n */
while (fibM < n) {
fibMMm2 = fibMMm1;
fibMMm1 = fibM;
fibM = fibMMm2 + fibMMm1;
}
// Marks the eliminated range from front
int offset = -1;
/* while there are elements to be inspected. Note that
we compare arr[fibMm2] with x. When fibM becomes 1,
fibMm2 becomes 0 */
while (fibM > 1) {
// Check if fibMm2 is a valid location
int i = min(offset + fibMMm2, n - 1);
/* If x is greater than the value at index fibMm2,
cut the subarray array from offset to i */
if (arr[i] < x) {
fibM = fibMMm1;
fibMMm1 = fibMMm2;
fibMMm2 = fibM - fibMMm1;
offset = i;
}
/* If x is greater than the value at index fibMm2,
cut the subarray after i+1 */
else if (arr[i] > x) {
fibM = fibMMm2;
fibMMm1 = fibMMm1 - fibMMm2;
fibMMm2 = fibM - fibMMm1;
}
/* element found. return index */
else
return i;
}
/* comparing the last element with x */
if (fibMMm1 && arr[offset + 1] == x)
return offset + 1;
/*element not found. return -1 */
return -1;
}
/* driver function */
int main(void)
{
int arr[]
= { 10, 22, 35, 40, 45, 50, 80, 82, 85, 90, 100,235};
int n = sizeof(arr) / sizeof(arr[0]);
int x = 235;
int ind = fibMonaccianSearch(arr, x, n);
if(ind>=0)
printf("Found at index: %d",ind);
else
printf("%d isn't present in the array",x);
return 0;
}
Code
// Java program for Fibonacci Search
import java.util.*;
class Fibonacci {
// Utility function to find minimum
// of two elements
public static int min(int x, int y)
{
return (x <= y) ? x : y;
}
/* Returns index of x if present, else returns -1 */
public static int fibMonaccianSearch(int arr[], int x,
int n)
{
/* Initialize fibonacci numbers */
int fibMMm2 = 0; // (m-2)'th Fibonacci No.
int fibMMm1 = 1; // (m-1)'th Fibonacci No.
int fibM = fibMMm2 + fibMMm1; // m'th Fibonacci
/* fibM is going to store the smallest
Fibonacci Number greater than or equal to n */
while (fibM < n) {
fibMMm2 = fibMMm1;
fibMMm1 = fibM;
fibM = fibMMm2 + fibMMm1;
}
// Marks the eliminated range from front
int offset = -1;
/* while there are elements to be inspected.
Note that we compare arr[fibMm2] with x.
When fibM becomes 1, fibMm2 becomes 0 */
while (fibM > 1) {
// Check if fibMm2 is a valid location
int i = min(offset + fibMMm2, n - 1);
/* If x is greater than the value at
index fibMm2, cut the subarray array
from offset to i */
if (arr[i] < x) {
fibM = fibMMm1;
fibMMm1 = fibMMm2;
fibMMm2 = fibM - fibMMm1;
offset = i;
}
/* If x is less than the value at index
fibMm2, cut the subarray after i+1 */
else if (arr[i] > x) {
fibM = fibMMm2;
fibMMm1 = fibMMm1 - fibMMm2;
fibMMm2 = fibM - fibMMm1;
}
/* element found. return index */
else
return i;
}
/* comparing the last element with x */
if (fibMMm1 == 1 && arr[n-1] == x)
return n-1;
/*element not found. return -1 */
return -1;
}
// driver code
public static void main(String[] args)
{
int arr[] = { 10, 22, 35, 40, 45, 50,
80, 82, 85, 90, 100,235};
int n = 12;
int x = 235;
int ind = fibMonaccianSearch(arr, x, n);
if(ind>=0)
System.out.print("Found at index: "
+ind);
else
System.out.print(x+" isn't present in the array");
}
}
Code
# Python3 program for Fibonacci search.
from bisect import bisect_left
# Returns index of x if present, else
# returns -1
def fibMonaccianSearch(arr, x, n):
# Initialize fibonacci numbers
fibMMm2 = 0 # (m-2)'th Fibonacci No.
fibMMm1 = 1 # (m-1)'th Fibonacci No.
fibM = fibMMm2 + fibMMm1 # m'th Fibonacci
# fibM is going to store the smallest
# Fibonacci Number greater than or equal to n
while (fibM < n):
fibMMm2 = fibMMm1
fibMMm1 = fibM
fibM = fibMMm2 + fibMMm1
# Marks the eliminated range from front
offset = -1
# while there are elements to be inspected.
# Note that we compare arr[fibMm2] with x.
# When fibM becomes 1, fibMm2 becomes 0
while (fibM > 1):
# Check if fibMm2 is a valid location
i = min(offset+fibMMm2, n-1)
# If x is greater than the value at
# index fibMm2, cut the subarray array
# from offset to i
if (arr[i] < x):
fibM = fibMMm1
fibMMm1 = fibMMm2
fibMMm2 = fibM - fibMMm1
offset = i
# If x is less than the value at
# index fibMm2, cut the subarray
# after i+1
elif (arr[i] > x):
fibM = fibMMm2
fibMMm1 = fibMMm1 - fibMMm2
fibMMm2 = fibM - fibMMm1
# element found. return index
else:
return i
# comparing the last element with x */
if(fibMMm1 and arr[n-1] == x):
return n-1
# element not found. return -1
return -1
# Driver Code
arr = [10, 22, 35, 40, 45, 50,
80, 82, 85, 90, 100,235]
n = len(arr)
x = 235
ind = fibMonaccianSearch(arr, x, n)
if ind>=0:
print("Found at index:",ind)
else:
print(x,"isn't present in the array");
Code
Sample Output
Input: a[] = {2, 3, 4, 10, 40}, x = 10
Output: 3
Element x is present at index 3.
Input: a[] = {2, 3, 4, 10, 40}, x = 11
Output: -1
Element x is not present.
Visualized
Note: For better Visualized Understanding visit our algorithm Visualizer