斐波那契查找

斐波那契数列 [1, 1, 2, 3, 5, 8, 13, 21, 34, 55 ] ，前后的比值会越来越接近 0.618 ，也就是黄金分割点。0.618也被公认为最具有审美意义的比例数字。斐波那契查找原理其实和二分查找原理差不多，只不过计算中间值 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，后面多余的用原数组最后的那个值填充，来看下代码。

public int search(int[] nums, int target) {
    int length = nums.length;
    int k = 0;// 根据k计算待查找的数组长度。
    while (length > f(k) - 1 || f(k) - 1 < 5)
        k++;
    // 斐波那契数列
    int[] fb = makeFbArray(f(k) - 1);
    // 生成新的数组。
    int[] tmp = Arrays.copyOf(nums, fb[k] - 1);
    for (int i = length; i < tmp.length; i++)
        tmp[i] = nums[length - 1];//用原数组最后的值填充。

    int left = 0;
    int right = length - 1;
    while (left <= right) {
        int mid = left + fb[k - 1] - 1; // 划分
        if (tmp[mid] == target) {
            // tmp 的后面是拼凑的，如果原数组长度很小，mid可能会超过原数组的长度，需要判断下。
            if (mid <= right) {
                return mid;
            } else {
                return right;
            }
        } else if (tmp[mid] > target) {//要查找的值在前面部分。
            right = mid - 1;
            k = k - 1;// 根据k计算下次查找的数组长度。
        } else {//要查找的值在后面部分。
            left = mid + 1;
            k = k - 2;// 根据k计算下次查找的数组长度。
        }
    }
    return -1;
}

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

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

实际上数组后面也可以不用填充，如果我们获取的元素下标超出数组的范围，直接返回数组的最后一个元素即可。

public int search(int[] nums, int target) {
    int length = nums.length;
    int k = 0;// 根据k计算待查找的数组长度。
    while (length > f(k) - 1 || f(k) - 1 < 5)
        k++;
    // 斐波那契数列
    int[] fb = makeFbArray(f(k) - 1);
    int left = 0;
    int right = length - 1;
    while (left <= right) {
        int mid = left + fb[k - 1] - 1; // 划分
        if (numVal(nums, mid) == target) {
            // tmp 的后面是拼凑的，如果原数组长度很小，mid可能会超过原数组的长度，需要判断下。
            if (mid <= right) {
                return mid;
            } else {
                return right;
            }
        } else if (numVal(nums, mid) > target) {//要查找的值在前面部分。
            right = mid - 1;
            k = k - 1;// 根据k计算下次查找的数组长度。
        } else {//要查找的值在后面部分。
            left = mid + 1;
            k = k - 2;// 根据k计算下次查找的数组长度。
        }
    }
    return -1;
}

private int numVal(int[] nums, int index) {
    if (index < nums.length)
        return nums[index];
    return nums[nums.length - 1];
}

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

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