04.斐波那契查找元素

归并排序

1.基本思想
2.排序过程
3.代码实现
4.如何优化
5.复杂度
6.使用场景

1.基本思想

斐波那契数列我们都知道{0,1,1,2,3,5,8,13,21,34,55}，前后的比值会越来越接近0.618，也就是黄金分割点。0.618也被公认为最具有审美意义的比例数字。

2.排序过程

斐波那契查找原理其实和二分法查找原理差不多，只不过计算中间值mid的方式不同，还有一点就是斐波那契查找的数组长度必须是f（k）-1，这样我们就可以把斐波那契数列进行划分f（k）-1=f（k-1）+f（k-2）-1=（f（k-1）-1）+1+（f（k-2）-1）；然后前面部分和后面部分都还可以继续进行划分。但实际上我们要查找的数组长度不可能都是f（k）-1，所以我们要补齐最后的部分，让数组的长度等于f（k）-1，让数组的最后一位数字把后面铺满。
比如我们查找的数组长度是21，而f（8）-1=21-1=20；小于21，所以f（8）-1是不行的，我们需要把数组长度变为f（9）-1=34-1=33，后面多余的我们都用原数组最后的那个值填充。

3.代码实现

代码如下所示

public static int fibonacciSearch(int[] array, int key) {
    if (array == null || array.length == 0)
        return -1;
    int length = array.length;
    int k = 0;
    while (length > fibonacci(k) - 1 || fibonacci(k) - 1 < 5) {
        k++;
    }
    int[] fb = makeFbArray(fibonacci(k) - 1);
    int[] temp = Arrays.copyOf(array, fb[k] - 1);
    for (int i = length; i < temp.length; i++) {
        temp[i] = array[length - 1];//用原数组最后的值填充
    }
    int low = 0;
    int hight = length - 1;
    while (low <= hight) {
        int middle = low + fb[k - 1] - 1;
        if (temp[middle] > key) {//要查找的值在前半部分
            hight = middle - 1;
            k = k - 1;
        } else if (temp[middle] < key) {//要查找的值在后半部分
            low = middle + 1;
            k = k - 2;
        } else {
            if (middle <= hight) {
                return middle;
            } else {
                return hight;
            }
        }
    }
    return -1;
}
  
private static int fibonacci(int n) {
    if (n == 0 || n == 1)
        return n;
    return fibonacci(n - 1) + fibonacci(n - 2);
}
  
public static int[] makeFbArray(int length) {
    int[] array = new int[length];
    array[0] = 0;
    array[1] = 1;
    for (int i = 2; i < length; i++)
        array[i] = array[i - 1] + array[i - 2];
    return array;
}

4.如何优化

其实斐波那契查找效率并没有那么高，我们再来看一下斐波那契查找的递归实现

public static int search(int[] array, int value) {
    if (array == null || array.length == 0) return -1;
    int length = array.length;
    int k = 0;
    while (length > fibonacci(k) - 1 || fibonacci(k) - 1 < 5) {
        k++;
    }
    int[] fb = makeFbArray(fibonacci(k) - 1);
    int[] temp = Arrays.copyOf(array, fb[k] - 1);
    for (int i = length; i < temp.length; i++) {
        temp[i] = array[length - 1];//用原数组最后的值填充
    }
    return fibonacciSearch(temp, fb, value, 0, length - 1, k);
}

public static int fibonacciSearch(int[] array, int[] fb, int value, int low, int hight, int k) {
    if (value < array[low] || value > array[hight] || low > hight) return -1;
    int middle = low + fb[k - 1] - 1;
    if (value < array[middle]) {
        return fibonacciSearch(array, fb, value, low, middle - 1, k - 1);
    } else if (value > array[middle]) {
        return fibonacciSearch(array, fb, value, middle + 1, hight, k - 2);
    } else {
        if (middle <= hight) {
            return middle;
        } else {
            return hight;
        }
    }
}

private static int fibonacci(int n) {
    if (n == 0 || n == 1) return n;
    return fibonacci(n - 1) + fibonacci(n - 2);
}

public static int[] makeFbArray(int length) {
    int[] array = new int[length];
    array[0] = 0;
    array[1] = 1;
    for (int i = 2; i < length; i++) array[i] = array[i - 1] + array[i - 2];
    return array;
}

5.复杂度

最坏情况下，时间复杂度为O(logn)，且其期望复杂度也为O(logn)。