C++ Program for Fibonacci Search
Descreption:
Fibonacci Search is a searching technique that uses Fibonacci numbers to search an element in sorted array. It is a comparison based technique and it return the index of the element we want to search and if element is not present in the array then -1 is returned.
Fibonacci numbers are defined as F(n) = F(n-1) + F(n-2) ,
F(1) = 1,
F(0) = 0,
First few fibonnaci numbers are 0,1,1,2,3,5,8,13.........
Properties of Fibonnaci Search :
1. Works for sorted array
2. Uses Divide and Conquer Algorithm
3. Divide array into unequal parts
4. Can be used for large array
Given a sorted array with n- elements, Find x in the array
Algorithm:
Step 1: Firstly, find F(k) - kth fibonacci number which is greater than or equal to the size of array (n).
Step 2: If F(k) = 0, then stop here and print -1.
Step 3: Set variable offset = -1.
Step 4: Set i = min( offset + F(k-2), n-1)
Step 5: Check
If X == Array[i] then, return i and stop the search.
If X > Array[i] then, k = k-1, offset = I and we need to repeat steps 4,5.
If X < Array[i] then, k = k-2 repeat steps 4,5.
C++ Program for Fibonnacci Search
#include <bits/stdc++.h>
using namespace std;
int fibonaciSearch(int arr[], int x, int n)
{
/* Here fibonacci numbers are initializing*/
int FK2 = 0; // (k-2)'th Fibonacci number
int FK1 = 1; // (k-1)'th Fibonacci number
int FK = FK2 + FK1; // k'th Fibonacci number
int offset = -1;
//FK stores smallest fibonacci number
//greater than or equal to n
while (FK < n)
{
FK2 = FK1;
FK1 = FK;
FK = FK2 + FK1;
}
while (fbK > 1)
{
// Check if FK2 is a valid location
int i = min(offset+FK2 , n-1);
if (arr[i] < x)
{
FK = FK1;
FK1 = FK2;
FK2 = FK - FK1;
offset = i;
}
else if (arr[i] > x)
{
FK = FK2;
FK1 = FK1 - FK2;
FK2 = FK - FK1;
}
else return i;
}
// comparing the last element with x
if(FK1 && arr[offset+1] == x)
return offset+1;
//element not found
return -1;
}
/* main function */
int main(void)
{
int n,i;
cout<<"\nEnter the total number of elements:";
cin>>n;
int arr[n];
cout<<"Enter elements in array\n";
for( i=0 ; i<n ; i++ )
{
cin>>arr[i];
}
int m = sizeof(arr)/sizeof(arr[0]);
int x;
cout<<"\nEnter element to be searched:";
cin>>x;
cout<<"Found at index: "<<fibonaciSearch(arr, x, m)<<"\n";
return 0;
}
Comments