算法原理：

斐波那契查找就是在二分查找的基礎(chǔ)上根據(jù)斐波那契數(shù)列進(jìn)行分割的。

1. 構(gòu)建一個(gè)斐波那契數(shù)列
2. 擴(kuò)展被查詢數(shù)列：在斐波那契數(shù)列找一個(gè)等于略大于查找表中元素個(gè)數(shù)的數(shù)F[n]，將原查找表擴(kuò)展為長(zhǎng)度為F[n](如果要補(bǔ)充元素，則補(bǔ)充重復(fù)最后一個(gè)元素，直到滿足F[n]個(gè)元素)
3. 查找元素：對(duì)擴(kuò)展后的被查詢數(shù)列進(jìn)行斐波那契分割，即F[n]個(gè)元素分割為前半部分F[n-1]個(gè)元素，后半部分F[n-2]個(gè)元素，找出要查找的元素在那一部分并遞歸，直到找到。

時(shí)間復(fù)雜度：

時(shí)間復(fù)雜度 O(log 2 n )

對(duì)比二分法查找：

二者時(shí)間復(fù)雜度一樣都是O(log 2 n )，但是與二分法查找相比，

斐波那契查找的優(yōu)點(diǎn)是它只涉及加法和減法運(yùn)算，而不用除法，而除法比加減法要占用更多的時(shí)間，

因此，斐波那契查找的運(yùn)行時(shí)間理論上比折半查找小，但是還是得視具體情況而定。

package com.study.java.al;

import java.util.Arrays;

/**
 *
 * 斐波那契查找算法
 * 步驟概述：
 * 1. 構(gòu)建一個(gè)斐波那契數(shù)列
 * 2. 擴(kuò)展被查詢數(shù)列：在斐波那契數(shù)列找一個(gè)等于略大于查找表中元素個(gè)數(shù)的數(shù)F[n]，將原查找表擴(kuò)展為長(zhǎng)度為F[n](如果要補(bǔ)充元素，則補(bǔ)充重復(fù)最后一個(gè)元素，直到滿足F[n]個(gè)元素)，
 * 3. 查找元素：對(duì)擴(kuò)展后的被查詢數(shù)列進(jìn)行斐波那契分割，即F[n]個(gè)元素分割為前半部分F[n-1]個(gè)元素，后半部分F[n-2]個(gè)元素，找出要查找的元素在那一部分并遞歸，直到找到。
 */

/**
 * @author ahdkkyxq
 */
public class FibonacciSearch {

    /**
     * @param args
     */
    public final static int MAXSIZE = 10;

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int[] f = fibonacci();
        // 打印fib數(shù)組
        System.out.println("斐波那契數(shù)列: "+Arrays.toString(f));
        int[] data = {1, 5, 15, 22, 25, 31, 39, 42, 47, 49, 59, 68, 88};
        System.out.println("被查詢數(shù)列: "+Arrays.toString(data));
        int search = 39;
        System.out.println("查詢目標(biāo): "+search);
        int position = fibonacciSearch(data, search);
        System.out.println("值" + search + "的元素位置為：" + position);
    }

    /**
     * 斐波那契數(shù)列
     *
     * @return
     */
    public static int[] fibonacci() {
        int[] f = new int[MAXSIZE];
        int i = 0;
        f[0] = 1;
        f[1] = 1;
        for (i = 2; i < MAXSIZE; i++) {
            f[i] = f[i - 1] + f[i - 2];
        }
        return f;
    }

    public static int fibonacciSearch(int[] data, int key) {
        int low = 0;
        int high = data.length - 1;
        int mid = 0;

        // 斐波那契分割數(shù)值下標(biāo)
        int k = 0;

        // 序列元素個(gè)數(shù)
        int i = 0;

        // 獲取斐波那契數(shù)列
        int[] f = fibonacci();

        // 獲取斐波那契分割數(shù)值下標(biāo)
        while (data.length > f[k] - 1) {
            k++;
        }

        // 創(chuàng)建臨時(shí)數(shù)組,長(zhǎng)度為fib的值-1，并復(fù)制原數(shù)組的內(nèi)容到新數(shù)組
        int[] temp = new int[f[k] - 1];
        for (int j = 0; j < data.length;j++){
            temp[j] = data[j];
        }
        // 序列補(bǔ)充至f[k]個(gè)元素
        // 補(bǔ)充的元素值為最后一個(gè)元素的值
        for (i = data.length; i < f[k] - 1; i++) {
            temp[i] = temp[high];
        }
        // 打印數(shù)組
        System.out.println("被查詢數(shù)組擴(kuò)容: "+Arrays.toString(temp));

        while (low <= high) {
            // low：起始位置
            // 前半部分有f[k-1]個(gè)元素，由于下標(biāo)從0開始
            // 則-1 獲取 黃金分割位置元素的下標(biāo)
            mid = low + f[k - 1] - 1;

            if (temp[mid] > key) {
                // 查找前半部分，高位指針移動(dòng)
                high = mid - 1;
                // （全部元素） = （前半部分）+（后半部分）
                // f[k] = f[k-1] + f[k-1]
                // 因?yàn)榍鞍氩糠钟衒[k-1]個(gè)元素，所以 k = k-1
                k = k - 1;
            } else if (temp[mid] < key) {
                // 查找后半部分，高位指針移動(dòng)
                low = mid + 1;
                // （全部元素） = （前半部分）+（后半部分）
                // f[k] = f[k-1] + f[k-1]
                // 因?yàn)楹蟀氩糠钟衒[k-1]個(gè)元素，所以 k = k-2
                k = k - 2;
            } else {
                // 如果為真則找到相應(yīng)的位置
                if (mid <= high) {
                    return mid;
                } else {
                    // 出現(xiàn)這種情況是查找到補(bǔ)充的元素
                    // 而補(bǔ)充的元素與high位置的元素一樣
                    return high;
                }
            }
        }
        return -1;
    }
}

運(yùn)算結(jié)果：

AAAA-07.png