斐波那契（黄金分割法）查找算法 （java）

一、介绍

1、斐波那契数列

形如1、1、2、3、5、8、13、21、34……的数列，并且从第三项开始，每项的值为前两项之和。并且随着数列的增大，数列前一个数字除以后一个数字的结果越接近黄金分割比。

二、算法思路

1.获取长度恰好为斐波那契数列中的数字的有序数组（长度不够即扩容），由斐波那契数列的性质可知：F(k) = F(k-1) + F(k-2)。我们将数组的总长度记为F(k),所以我们可以将数组分割为两部分：前部分的长度为F(k-1),后部分的长度为F(k-2)。前部分长度比后部分长度近似黄金分割比。
在这里插入图片描述

2.在两部分的交界处寻找到一个中间点，将需要查找的值与中间点比较，若小于中间点，说明目标值在前半部分，由于前半部分的长度也为斐波那契数列中的数值，所以可以直接重复第一步操作，分割数组，比较查值。若目标值大于中间点，同理。

三、代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
 public int fiboReserch(int arr[], int value) { //arr为目标有序数组， value为需要查找的值
     	int[] fibo = {1, 1, 2, 3, 5, 8, 13, 21, 34} //斐波那契数组
        int k = 0; //与数组长度适应的斐波那契数组索引
        int left = 0; //数组左端索引
        int right = arr.length - 1; //数组右端索引，初始为最后一位
     	int mid; //分割点
        while (arr.length > fibo[k]) {
            k++;
        } // 找到一个大于或等于数组长度的斐波那契数组中的值
            int[] ints = arr;
            if (arr.length < fibo[k]) {
                ints = Arrays.copyOf(arr, fibo[k]);
                for (int i = right + 1; i < ints.length; i++) {
                    ints[i] = arr[right];
                }
            } // 若查找到的斐波那契数组的值大于目标数组，则将数组扩容到该值，
     //并且将扩容的空间全部加入数组原本最后一位数字的数值。
            while (left <= right) { //当右索引小于左索引时，跳出循环
                mid = left + fibo[k - 1] - 1; //确定中间点(近似黄金分割点)
                if (ints[mid] < value) {
                    left = mid + 1;
                    k -= 2; //因为被分割的右方部分长度为F(k-2),所以重置k的值
                            //为k=k-2，这样便于下一次循环寻找中间点。
                } else if (ints[mid] > value) {
                    right = mid; //为提高效率，也可写成 right = mid - 1,但是这样
                    			//左边数组的长度不再满足斐波那契数组，如果数组长度长，
                    		    //循环多次可能会导致更加偏离黄金分割，但是并不影响查找结果
                    
                     k -= 1; //因为被分割的左方部分长度为F(k-1),所以重置k的值
                            //为k=k-1，这样便于下一次循环寻找中间点。
                } else {
                    if (right >= mid) {
                        return mid;//返回目标索引
                    }
                    else {
                        return right;
                    } //(right < mid的情况)如果数组经过扩容后，形如{...... , 56, 56, 						//56, 56, 56},并且查找的值也为56，因为right指向的是原本数组的尾部，					//也就是第一个56，但是经过(mid = left + fibo[k - 1] - 1;)变换，mid					//会大于right，此时返回的索引就是扩容后的索引，严重失真，所以直接返回						//right
                }
            }
        return -1; // 没查找到目标数字返回-1
}