对于斐波那契数列：1、1、2、3、5、8、13、21、34、55、89……（也可以从0开始），前后两个数字的比值随着数列的增加，越来越接近黄金比值0.618。比如这里的89，把它想象成整个有序表的元素个数，而89是由前面的两个斐波那契数34和55相加之后的和，也就是说把元素个数为89的有序表分成由前55个数据元素组成的前半段和由后34个数据元素组成的后半段，那么前半段元素个数和整个有序表长度的比值就接近黄金比值0.618，假如要查找的元素在前半段，那么继续按照斐波那契数列来看，55 = 34 + 21，所以继续把前半段分成前34个数据元素的前半段和后21个元素的后半段，继续查找，如此反复，直到查找成功或失败，这样就把斐波那契数列应用到查找算法中了。如下图：
从图中可以看出，当有序表的元素个数不是斐波那契数列中的某个数字时，需要把有序表的元素个数长度补齐，让它成为斐波那契数列中的一个数值，当然把原有序表截断肯定是不可能的，不然还怎么查找。然后图中标识每次取斐波那契数列中的某个值时(F[k])，都会进行-1操作，这是因为有序表数组位序从0开始的，纯粹是为了迎合位序从0开始。(fib[k]是数组的长度,而数组索引是从0开始的,所以需要进行-1来跟数组索引匹配)
————————————————
mid = low + f[k - 1] - 1, k代表斐波那契的第几个元素
f[k - 1] = (f[k - 1] - 1) + (f[k - 1] - 1) + 1
也就是只要顺序表的长度为f[k ] - 1则可以将表分割成长度为f[k - 1] - 1和f[k - 2] - 1的两段，
mid = low + f[ k - 1] - 1
但原来的顺序表长度不一定刚好等于f[k - 1]，因此需要将其长度增加到f[k - 1]
// 生成斐波那契数组，因为斐波那契相邻的数之间都很接近0.618
// {1，1，2，3，5，8，13，21，34，55}
// f[k] = f[k - 1] + f[k - 2];
public static int[] f(){
int[] f = new int[20];
f[0] = 1;
f[1] = 1;
for (int i = 2; i < f.length; i++){
f[i] = f[i - 1] + f[i - 2];
}
return f;
}
// mid = low + F(k - 1) - 1
public static int search(int[] arrs, int key) {
int low = 0;
int high = arrs.length - 1;
int k = 0;
int mid = 0;
int[] f = f();
// 找出f中最接近arrs.length的值，因为high = arrs.length - 1，所以f[k] - 1
while(high > f[k] - 1){
k++;
}
// 因为f[k]的长度可能大于arrs.length，所以要用进行补全，由于是递增的，所以用arrs中的最大值进行补足
int[] temp = Arrays.copyOf(arrs, f[k]);
for (int i = high + 1; i < temp.length; i++) {
temp[i] = arrs[high];
}
while (low <= high){
// 中间值求取，套公式
mid = low + f[k - 1] - 1;
if (key < temp[mid]){ // 查看是否在左半段
high = mid - 1; // 到左半段进行查找
k--; // 按照黄金分割f[k-1] + f[k-2] = f[k], 左半段分为按f[k - 1]的长度，所以此处减去1，去左半段继续找mid
}else if (key > temp[mid]){ // 查看是否在右半段
low = mid + 1; // 到右半段进行查找
k -= 2; // 按照黄金分割f[k-1] + f[k-2] = f[k], 右半段是f[k - 2]的长度，所以此处减去2，去右半段继续找mid
}else {
// 如果mid > high的话说明查找到的是补全值
return Math.min(mid, high);
}
}
return -1;
}