Data Structure and Algorithm analysis (Fibonacci Lookup)

Fibonacci search is a search technique of single peak function in interval, which is segmented according to Fibonacci sequence on the basis of binary search. Find a Fibonacci number F[n] equal to or slightly greater than the number of elements in the lookup table. If the original lookup table is less than F[n], add the last element until F[n] elements are satisfied. After completion, Fibonacci segmentation is carried out, that is, F[n] elements are divided into the first half of F[n-1] elements and the second half of F[n-2] elements. Search forward or backward according to the relationship between values until it is found. If it is never found, -1 is returned.

Example:

public class Program {
 
    public static void Main(string[] args) {
        int[] array = { 8.11.21.28.32.43.48.56.69.72.80.94 };
        CalculateFibonacci();
 
        Console.WriteLine(FibonacciSearch(array, 80));
 
        Console.ReadKey();
    }
 
    private const int MAXSIZE = 47;
 
    private static int[] _fibonacciArray = new int[MAXSIZE];
 
    private static void CalculateFibonacci() {
        _fibonacciArray[0] = 1;
        _fibonacciArray[1] = 1;
        // Calculate Fibonacci number, use array to save intermediate knot to prevent double calculation,
        // Note that the Fibonacci number overflows the integer range when MAXSIZE is 48.
        / / 1,1,2,3,5,8,13,21,34,55,89...
        for(int i = 2; i < _fibonacciArray.Length; i++)
            _fibonacciArray[i] = _fibonacciArray[i - 1] + _fibonacciArray[i - 2];
    }
 
    private static int FibonacciSearch(int[] array, int key) {
        int length = array.Length;
        int low = 0, high = length - 1, mid, k = 0;
 
        // Find the nearest Fibonacci number (k=6, 13)
        int[] banlance;
        while(length > _fibonacciArray[k])
            k++;
 
        // The number of arrays must be _fibonacciArray[k], so an intermediate balanced array is used
        if(length < _fibonacciArray[k]) {
            banlance = new int[_fibonacciArray[k]];
            for(int i = 0; i <= length - 1; i++)
                banlance[i] = array[i];
        } else {
            banlance = array;
        }
 
        // Balance the last half of the array with the last value
        for(int i = length; i < _fibonacciArray[k]; i++)
            banlance[i] = banlance[length - 1];
 
        // The following process is similar to binary search
        while(low <= high) {
            mid = low + _fibonacciArray[k - 1] - 1;
            if(banlance[mid] > key) {
                high = mid - 1;
                k--;
            } else if(banlance[mid] < key) {
                low = mid + 1;
                k -= 2;
            } else {
                // Prevent index from going out of bounds
                if(mid <= length - 1)
                    return mid;
                return length - 1; }}// Return -1 if not found
        return - 1; }}Copy the code

The worst case Fibonacci search time is O(logn).