算法原理：
斐波那契查找就是在二分查找的基礎上根據(jù)斐波那契數(shù)列進行分割的含思。
- 構建一個斐波那契數(shù)列
- 擴展被查詢數(shù)列：在斐波那契數(shù)列找一個等于略大于查找表中元素個數(shù)的數(shù)F[n]，將原查找表擴展為長度為F[n](如果要補充元素险绘，則補充重復最后一個元素毒涧，直到滿足F[n]個元素)
- 查找元素：對擴展后的被查詢數(shù)列進行斐波那契分割，即F[n]個元素分割為前半部分F[n-1]個元素鉴分，后半部分F[n-2]個元素劣砍，找出要查找的元素在那一部分并遞歸惧蛹，直到找到。
時間復雜度：
時間復雜度 O(log 2 n )
對比二分法查找：
二者時間復雜度一樣都是O(log 2 n )刑枝，但是與二分法查找相比香嗓，
斐波那契查找的優(yōu)點是它只涉及加法和減法運算，而不用除法装畅，而除法比加減法要占用更多的時間靠娱，
因此，斐波那契查找的運行時間理論上比折半查找小掠兄，但是還是得視具體情況而定饱岸。
package com.study.java.al;
import java.util.Arrays;
/**
*
* 斐波那契查找算法
* 步驟概述：
* 1. 構建一個斐波那契數(shù)列
* 2. 擴展被查詢數(shù)列：在斐波那契數(shù)列找一個等于略大于查找表中元素個數(shù)的數(shù)F[n]，將原查找表擴展為長度為F[n](如果要補充元素徽千，則補充重復最后一個元素，直到滿足F[n]個元素)汤锨，
* 3. 查找元素：對擴展后的被查詢數(shù)列進行斐波那契分割双抽，即F[n]個元素分割為前半部分F[n-1]個元素，后半部分F[n-2]個元素闲礼，找出要查找的元素在那一部分并遞歸牍汹，直到找到。
*/
/**
* @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("查詢目標: "+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ù)值下標
int k = 0;
// 序列元素個數(shù)
int i = 0;
// 獲取斐波那契數(shù)列
int[] f = fibonacci();
// 獲取斐波那契分割數(shù)值下標
while (data.length > f[k] - 1) {
k++;
}
// 創(chuàng)建臨時數(shù)組,長度為fib的值-1柬泽，并復制原數(shù)組的內(nèi)容到新數(shù)組
int[] temp = new int[f[k] - 1];
for (int j = 0; j < data.length;j++){
temp[j] = data[j];
}
// 序列補充至f[k]個元素
// 補充的元素值為最后一個元素的值
for (i = data.length; i < f[k] - 1; i++) {
temp[i] = temp[high];
}
// 打印數(shù)組
System.out.println("被查詢數(shù)組擴容: "+Arrays.toString(temp));
while (low <= high) {
// low：起始位置
// 前半部分有f[k-1]個元素慎菲，由于下標從0開始
// 則-1 獲取 黃金分割位置元素的下標
mid = low + f[k - 1] - 1;
if (temp[mid] > key) {
// 查找前半部分，高位指針移動
high = mid - 1;
// （全部元素） = （前半部分）+（后半部分）
// f[k] = f[k-1] + f[k-1]
// 因為前半部分有f[k-1]個元素锨并，所以 k = k-1
k = k - 1;
} else if (temp[mid] < key) {
// 查找后半部分露该，高位指針移動
low = mid + 1;
// （全部元素） = （前半部分）+（后半部分）
// f[k] = f[k-1] + f[k-1]
// 因為后半部分有f[k-1]個元素，所以 k = k-2
k = k - 2;
} else {
// 如果為真則找到相應的位置
if (mid <= high) {
return mid;
} else {
// 出現(xiàn)這種情況是查找到補充的元素
// 而補充的元素與high位置的元素一樣
return high;
}
}
}
return -1;
}
}
運算結果：
AAAA-07.png
