Similarities with Binary Search:
Works for sorted arrays
A Divide and Conquer Algorithm.
Has Log n time complexity.
Differences with Binary Search:
Fibonacci Search divides given array in unequal parts
Binary Search uses division operator to divide range. Fibonacci Search doesn’t use /, but uses + and -. The division operator may be costly on some CPUs.
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.
This is based on Fibonacci series :
F(n+1)=F(n)+F(n-1)
where F(i) is the ith number of the Fibonacci series where F(0) and F(1) are defined as 0 and 1 respectively.
The first few Fibonacci numbers are:
0,1,1,2,3,5,8,13....
F(0) = 0
F(1) = 1
F(2) = F(1) + F(0) = 1 + 0 = 1
F(3) = F(2) + F(1) = 1 + 1 = 2
F(4) = F(3) + F(2) = 1 + 2 = 3 and so continues the series
Algorithm: Let the length of given array be n [0...n-1] and the element to be searched be x.
Find the smallest Fibonacci number greater than or equal to n. Let this number be fb(M) [m’th Fibonacci number]. Let the two Fibonacci numbers preceding it be fb(M-1) [(m-1)’th Fibonacci number] and fb(M-2) [(m-2)’th Fibonacci number].
While the array has elements to be checked:
-> Compare x with the last element of the range covered by fb(M-2)
-> If x matches, return index value
-> Else if x is less than the element, move the third Fibonacci variable two Fibonacci down, indicating removal of approximately two-third of the unsearched array.
-> Else x is greater than the element, move the third Fibonacci variable one Fibonacci down. Reset offset to index. Together this results into removal of approximately front one-third of the unsearched array.
Since there might be a single element remaining for comparison, check if fbM1 is '1'. If Yes, compare x with that remaining element. If match, return index value.
Example:
Let the length of given array be n [0...n-1] and the element to be searched be x.
0 1 2 3 4 //index
2 3 5 7 8 // value
x=7 int arr[10];
N = sizeof(arr)/sizeof(arr[0])= 5
// Initialize fibonacci numbers
fibonacci(int arr[], int x, int n)
{
fbM2 = 0 // (m-2)'th Fibonacci number
fbM1 = 1; // (m-1)'th Fibonacci number
fbM = fbM2 + fbM1; // m'th Fibonacci
// Marks the eliminated range from front
offset = -1;
// fbM is going to store the smallest Fibonacci
number greater than or equal to n
while (fbM < n)
{
fbM2 = fbM1;
fbM1 = fbM;
fbM = fbM2 + fbM1;
}
// fbM is going to store the smallest Fibonacci
number greater than or equal to n
while (fbM < n)
{
fbM2 = fbM1;
fbM1 = fbM;
fbM = fbM2 + fbM1;
}
// fbm=0+1=1;
while (2 < 5)
{
fbM2 =1 ;
fbM1 = 2;
fbM = 3;
}
while (3 < 5)
{
fbM2 =2 ;
fbM1 = 3;
fbM = 5;
}
//while there are elements to be inspected. Note that we compare arr[fibM2] with x.
When fbM becomes 1, fbM2 becomes 0
while (fbM > 1) // 5>1
{
int i = min(offset+fbM2, n-1); // min(-1+2,4)
i=1
int min(int x, int y)
{
return (x<=y)? x : y;
}
if (arr[i] < x) // 3<7
{
fbM = fbM1; fbM=3
fbM1 = fbM2; fbM1=2
fbM2 = fbM - fbM1; fbM2= 1
offset = i; offset=1
}
else if (arr[i] > x)
{
fbM = fbM2;
fbM1 = fbM1 - fbM2;
fbM2 = fbM - fbM1;
}
else return i;
//element found. return index
} // close while loopif (arr[i] < x) // 3<7
{
fbM = fbM1; fbM=3
fbM1 = fbM2; fbM1=2
fbM2 = fbM - fbM1; fbM2= 1
offset = i; offset=1
}
while (fbM > 1) // 3>1
{
int i = min(offset+fbM2, n-1); // min(1+2,4)
i=3
if (arr[i] < x) // 7<7
{
fbM = fbM1;
fbM1 = fbM2;
fbM2 = fbM - fbM1;
offset = i;
}
else if (arr[i] > x) // 7>7
{
fbM = fbM2;
fbM1 = fbM1 - fbM2;
fbM2 = fbM - fbM1;
}
else return i;
//element found. return index
} // close while loop/* comparing the last element with x */
if(fbM1 && arr[offset+1]==x)
return offset+1;
/*element not found. return -1 */
return -1;
- Worst case time complexity: O(logn)
- Average case time complexity: O(logn)
- Best case time complexity: O(n)
- Space complexity: O(1)
0 Comments