Fibonacci search (golden section)

On the basis of interpolation search , You can fix the proportional value to 0.618（ The golden section ）, Each time you look it up, follow （mid Number of first elements ）/（mid Number of last elements ）=0.618 To determine the location of the next search . In order to meet the initial state , The number of array elements conforms to a certain value in the Fibonacci sequence , You need to fill the array before you find it .

C Code ：

#include <stdio.h>

#define MAXSIZE 20

void fibonacci(int *f)
{
    
	int i;

	f[0] = 1;
	f[1] = 1;
	
	for(i=2; i < MAXSIZE; ++i)
	{
    
		f[i] = f[i-2] + f[i-1];

	}
}

int fibonacci_search(int *a,int key,int n)
{
    
	int low = 0;
	int high = n - 1;
	int mid = 0;
	int k = 0;
	int F[MAXSIZE];
	int i;

	fibonacci(F);
	
	while( n > F[k]-1 ) //F[k] Can be understood as the number of elements 
	{
    
		++k;
	}

	for( i=n; i < F[k]-1; ++i)
	{
    
		a[i] = a[high];
	}

	while( low <= high )
	{
    
		mid = low + F[k-1] - 1;

		if( a[mid] > key )
		{
    
			high = mid - 1;
			k = k - 1;
		}
		else if( a[mid] < key )
		{
    
			low = mid + 1;
			k = k - 2;
		}
		else
		{
    
			if( mid <= high ) 
			{
    
				return mid;
			}
			else
			{
    
				return high;
			}
		}
	}

	return -1;
}

int main()
{
    
	
	int a[MAXSIZE] = {
    1, 5, 15, 22, 25, 31, 39, 42, 47, 49, 59, 68, 88};
	int key;
	int pos;

	printf(" Please enter the number you want to find :");
	scanf("%d", &key);
	
	pos = fibonacci_search(a, key, 13);
	
	if( pos != -1 )
	{
    
		printf("\n Find success ！  keyword  %d  The location is : %d\n\n", key, pos);
	}
	else
	{
    
		printf("\n Element not found in array :%d\n\n", key);
	}
		
	return 0;
}