1, Algorithm Introduction

Fibonacci sequence, also known as golden section sequence, refers to such a sequence: 1, 1, 2, 3, 5, 8, 13, 21,... Mathematically, Fibonacci is defined as follows: F(1)=1, F(2)=1, F(n)=f(n-1)+F(n-2) (n > = 2). The ratio of the next two numbers in the sequence tends to the golden ratio (0.618).

Fibonacci search algorithm (golden section search algorithm): Mid = Low + F (k-1) - 1; F for Fibonacci series

Understanding of F(k-1)-1:

From the properties of Fibonacci sequence f [k] = f [k-1] + F [K-2], we can get (F[k]-1) = (F[k-1]-1) + (F[k-2]-1) +1.

Note: as long as the length of the sequence table is F[K]-1, the table can be divided into two segments with the length of F[k-1]-1 and F[k-2]-1, as shown in the figure above. So the middle position is mid=low+F(k-1)-12)

Similarly, each sub segment can be divided in the same way.

But the length n of the sequence table is not necessarily equal to F[k]-1, so we need to increase the length n of the original sequence table to F[k]-1. As long as the value of K here can make F[k]-1 exactly greater than or equal to N, it can be obtained from the following code. After the length of the sequence table is increased, the new positions (from n+1 to F[k]-1 positions) can be assigned as the value of N position.

2, Code implementation

/**
 * Generating Fibonacci series
 * @param fib: Pointer to an array of Fibonacci sequences
 * @param size: Fibonacci sequence length
 */
void produce_fib(int *fib, int size)
{
    int i;

    fib[0] = 1;
    fib[1] = 1;

    for (i = 2; i < size; i++)
    {
        fib[i] = fib[i - 1] + fib[i - 2];
    }
}

/**
 * Fibonacci search. If the search is successful, the bit order will be returned, otherwise - 1 will be returned
 * @param data: Ordered table array
 * @param length: Number of ordered table elements
 * @param searchValue: Keywords to be found
 */
int fibonacci_search(int *data, int length, int searchValue)
{
    int low, high, mid, k, i, fib[100];

    low = 0;
    high = length - 1;

    produce_fib(fib, 100);

    k = 0;
    // Find the closest maximum sequence value of the number of elements in the Fibonacci sequence
    while (high > fib[k] - 1)
    {
        k++;
    }

    // Complete the order table
    for (i = length; i <= fib[k] - 1; i++)
    {
        data[i] = data[high];
    }

    while (low <= high)
    {
        mid = low + fib[k - 1] - 1;   // Golden section according to Fibonacci series

        if (data[mid] == searchValue)
        {
            if (mid <= length - 1)
            {
                return mid;
            }
            else
            {
                // Indicates that the data element found is the completion value
                return length - 1;
            }
        }

        if (data[mid] > searchValue)
        {
            high = mid - 1;
            k = k - 1;
        }

        if (data[mid] < searchValue)
        {
            low = mid + 1;
            k = k - 2;
        }
    }
    return -1;
}

void test_6()
{

    int data[] = {1,3,5,7,9,11,13,15,17,19,21};

    int result = fibonacci_search(data, 11, 19);
    cout<<"result:"<<result<<endl;
}

int main() {
    test_6();
    return 0;
}

3, Algorithm analysis

The time complexity of Fibonacci search is still O(log2n), but compared with half search, the advantage of Fibonacci search is that it only involves addition and subtraction, not division, and division takes more time than addition and subtraction. Therefore, the running time of Fibonacci search is theoretically smaller than half search, but it depends on the specific situation.