Fibonacci search

Fibonacci search algorithm.with good explanation

2. Fibonacii Search
-Applied on sorted arrays
-It uses Fibonacci series to determine the index position to be
searched in the array.
-Steps
-1.Find out a fibonacci number (F
m
) that is greater than or equal to
the size of the array. Then
-2. Compare the item with the element at F
m-1
position in the array.
-3. If they are equal, search is successful, element is at F
m-1
+1.
-4. If the item is smaller, it is searched in the sublist left to F
m-1..
-5. If the item is greater, it is searched in the sublist right to F
m-1..
-

If

item is not found, again the fibonacci number >= size of the
sublist to be searched is taken, and the whole process is repeated
until the desired element is found or the sublist is reduced to a
single element that is not equal to item.

3. Fibonacii search Tree

4. No of records n=33(1 less than
34)
0 1 2 3 4 5 6 7 8 910111213 14151617181920
4 6 81015161718192022242628 29303233353738
21 22 23 24 25 26 27 28 29 30 31 32
39 40 41 42 43 44 45 46 47 48 49 50
Search 45 , 8

5. 01 23 45 6 7 8 9
01 12 35 8132134

6. Algorithm Fibonacii_Search(A, n, item)
{
int flag, first, last, loc, index;
flag=0;first=0;loc=-1; last=n-1;
while( flag !=1 && first<=last)
{
index =return_finonacci(n);//returns F
m-1
th Fibonacci no.
if ( item = = A[index +first])
{
flag=1;
loc =index;
break ;
}
else if (item > A[index +first])
{
first=first + index +1;
}

7. else
{
last = first + index - 1 ;
}
n=last-first+1;
} //end of while
if (flag= =1)
return (loc+first+1);
else
return -1 ;//item not found
}

8. return_finonacci(n)
{
int a, b, c;
a =b = c =1;
if (n ==0 || n ==1)
return 0;
else
{
while (c < n)
{
c = a + b;
a = b;
b =c;
}
}
return a;
}

9. Analysis
•The complexity of Fibonacci search is O(log
2
n)
•The performance of Fibonacci search is poor than
binary search.
•However, binary search involves division operation ,
where as in Fibonacci search only addition and
subtraction operation is involved. Average
performance of Fibonacci search may be better than
binary search on computers where division is more
time consuming than addition or subtraction.

10. -It is applied on sorted arrays.
-It is based on the assumption that the elements
in the list are uniformly distributed.
-Determines the location of the item to be
searched according to the magnitude of the
item relative to the first and last elements of
the array.
Interpolation search

11. 1 7 13 19 25 31 37
0 1 2 3 4 5 6
Search 13
Elements in the array are uniformly distributed.
Mid = 0+(6-0)*((13-1)/(37 -1))
= 6*(12/36)
= 6 * 0.33
=2

12. Interpolation Search
interpol_search(ARR, size, item)
1. set low=0, high=size-1, flag=-1
2. while low <= high
if high = low
if ARR[low]=item
set flag=low
end if
Break
end if

13. Contd…
set mid=low+(high-low)*((item-ARR[low])/(ARR[high]-ARR[low]))
if ARR[mid]=item
set flag=mid
break
else if ARR[mid] > item
set high = mid – 1
else
set low = mid + 1
end if
3. return(flag)
4. end

14. Function for interpolation search
int interpol_search(int A[], int size, int item)
{
int mid, low, high, flag=-1;
low=0;
high=size-1;
while (low<=high)
{
if (high==low)
{
if (A[low]==item)
flag=low;
break;
}

15. mid=low+(high-low)*(float) (item-A[low]) / (A[high]-A[low]);
if(A[mid]==item)
{
flag=mid;
break;
}
else if (A[mid] > item)
high=mid-1;
else
low=mid+1;
}
return(flag);
}

16. Analysis
•Performance of interpolation search is highly
dependent on the distribution of elements in the list.
•In the best case , complexity is log(log(n))
•If the elements are not uniformly distributed , then
interpolation search gives a very poor performance.