1.基本介紹
黃金分割點(diǎn)是指把一條線段分割為兩部分，使其中一部分與全長(zhǎng)之比等于另一部分與這部分之比跺讯。取其前三位數(shù)字的近似值是 0.618震庭。由于按此比例設(shè)計(jì)的造型十分美麗，因此稱為黃金分割担钮，也稱為中外比。這是一個(gè)神奇的數(shù)字尤仍，會(huì)帶來(lái)意向不大的效果箫津。
斐波那契數(shù)列 {1, 1, 2, 3, 5, 8, 13, 21, 34, 55 } 發(fā)現(xiàn)斐波那契數(shù)列的兩個(gè)相鄰數(shù) 的比例，無(wú)限接近 黃金分割值0.618
2. 斐波那契(黃金分割法)原理
斐波那契查找原理與前兩種相似宰啦，僅僅改變了中間結(jié)點(diǎn)（mid）的位置苏遥，mid 不再是中間或插值得到，而是位于黃金分割點(diǎn)附近赡模，即 mid=low+F(k-1)-1（F 代表斐波那契數(shù)列）
對(duì)F(k-1)-1的理解:
由斐波那契數(shù)列 F[k]=F[k-1]+F[k-2] 的性質(zhì)田炭，可以得到 （F[k]-1）=（F[k-1]-1）+（F[k-2]-1）+1 。該式說(shuō)明：只要順序表的長(zhǎng)度為 F[k]-1漓柑，則可以將該表分成長(zhǎng)度為 F[k-1]-1 和 F[k-2]-1 的兩段教硫，即如上圖所示。從而中間位置為 mid=low+F(k-1)-1
類似的辆布，每一子段也可以用相同的方式分割
但順序表長(zhǎng)度 n 不一定剛好等于 F[k]-1瞬矩，所以需要將原來(lái)的順序表長(zhǎng)度 n 增加至 F[k]-1。這里的 k 值只要能使得 F[k]-1 恰好大于或等于 n 即可锋玲，由以下代碼得到,順序表長(zhǎng)度增加后景用，新增的位置（從 n+1 到 F[k]-1 位置），都賦為 n 位置的值即可惭蹂。
while(n>fib(k)-1)
k++;
3.應(yīng)用案例
請(qǐng)對(duì)一個(gè)有序數(shù)組進(jìn)行斐波那契查找 {1,8, 10, 89, 1000, 1234} 伞插，輸入一個(gè)數(shù)看看該數(shù)組是否存在此數(shù)割粮，并且求出下標(biāo)，如果沒(méi)有就提示"沒(méi)有這個(gè)數(shù)"媚污。
import java.util.Arrays;
/**
* @author xuyuyong
* @create 2021-05-07 18:02
* @content
*/
public class FibonacciSearch {
public static int maxSize = 20;
public static void main(String[] args) {
int [] arr = {1,8, 10, 89, 1000, 1234};
System.out.println("index=" + fibSearch(arr, 189));
}
/**
* 因?yàn)楹竺嫖覀?mid=low+F(k-1)-1穆刻，需要使用到斐波那契數(shù)列，因此我們需要先獲取到一個(gè)斐波那契數(shù)列
* 非遞歸方法得到一個(gè)斐波那契數(shù)列
*/
public static int[] fib() {
int[] f = new int[maxSize];
f[0] = 1;
f[1] = 1;
for (int i = 2; i < maxSize; i++) {
f[i] = f[i - 1] + f[i - 2];
}
return f;
}
/**
* 編寫斐波那契查找算法
* 使用非遞歸的方式編寫算法
* @param a 數(shù)組
* @param key 我們需要查找的關(guān)鍵碼(值)
* @return 返回對(duì)應(yīng)的下標(biāo), 如果沒(méi)有 -1
*/
public static int fibSearch(int[] a, int key) {
int low = 0;
int high = a.length - 1;
//表示斐波那契分割數(shù)值的下標(biāo)
int k = 0;
//存放mid值
int mid = 0;
//獲取到 斐波那契 數(shù)列
int[] f = fib();
while (high > f[k] - 1) {
k ++;
}
//因?yàn)?f[k] 值 可能大于 a 的長(zhǎng)度, 因此 我們需要使用 Arrays 類, 構(gòu)造一個(gè)新的數(shù)組, 并指向temp[]
//不足的部分會(huì)使用 0 填充
int[] temp = Arrays.copyOf(a, f[k]);
//實(shí)際上需求使用 a 數(shù)組最后的數(shù)填充 temp
//舉例:
//temp = [1,8, 10, 89, 1000, 1234, 0, 0] => {1,8, 10, 89, 1000, 1234, 1234, 1234,}
for (int i = high + 1; i < temp.length; i++) {
temp[i] = a[high];
}
// 使用 while 來(lái)循環(huán)處理, 找到我們的數(shù) key
while (low <= high) {
mid = low + f[k - 1];
//我們應(yīng)該繼續(xù)向數(shù)組的前面查找(左邊)
if (key < temp[mid]) {
high = mid - 1;
//why是 k-1
//說(shuō)明
//1. 全部元素 = 前面的元素 + 后邊元素
//2. f[k] = f[k - 1] + f[k - 2]
//因?yàn)?前面 f[k - 1]個(gè)元素, 所以可以繼續(xù)拆分 f[k -1] = f[k - 2] + f[k - 3]
//即 在 f[k-1] 的前面繼續(xù)查找 k--
//即下次循環(huán) mid = f[k-1-1]-1
k--;
// 我們應(yīng)該繼續(xù)向數(shù)組的后面查找(右邊)
} else if ( key > temp[mid]) {
low = mid + 1;
//為什么是 k -=2
//說(shuō)明
//1. 全部元素 = 前面的元素 + 后邊元素
//2. f[k] = f[k-1] + f[k-2]
//3. 因?yàn)楹竺嫖覀冇?f[k-2] 所以可以繼續(xù)拆分 f[k-1] = f[k-3] + f[k-4]
//4. 即在 f[k-2] 的前面進(jìn)行查找 k -=2
//5. 即下次循環(huán) mid = f[k - 1 - 2] - 1
k -= 2;
} else { //找到
//需要確定杠步，返回的是哪個(gè)下標(biāo)
if(mid <= high) {
return mid;
} else {
return high;
}
}
}
return -1;
}
}
