查找算法入门教程-黄金分割查找法(斐波拉契)

前面我们学习了常见查找算法的插值和二分查找,这节我们来学习黄金分割查找法,也称斐波拉契,想必大家对斐波拉契函数f(k) = f(k-1) +f(k -2)都知到,我们的黄金分割法用到了斐波拉契函数,接下来我们一起来学习

黄金分割法介绍

黄金分割是指将一条线段分割成两部分,使其中一部分与全长之比等于另一部分与这部分之比,取其全三位的数字的近似值接近0.618,因此该点称为黄金分割点.

斐波拉契数列

如{1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144},我们会发现斐波拉契数列的每相邻两个数的比例是接近0.618,存在的函数为f(k) = f(k-1) +f(k -2),我们来看看黄金分割的原理

黄金分割原理

黄金分割查找的过程是跟二分和插值是类似的,唯一的区别是改变mid(中间值)的位置,对于黄金分割而言,mid不在是通过二分查找和插值查找那样计算得到的,而是遵循这样一个函数mid = F(k -1) -1;也就是我们的mid是接近于黄金分割点的附近,其中F代表为斐波拉契数列,我们来看张图:

斐波拉契数列.png

简单的来介绍下图中的所涉及到的变量
其中 low表示: 数列的左边索引也就是(left)
high表示:数列的右边索引也就是(right)

接着我们来理解下mid = F(k -1) -1过程

• 我们都知道斐波拉契数列遵循f(k) = f(k-1) +f(k -2)性质,因此我们可以得到(F[k] -1) = (F[k -1] -1) +(F[k-2] -1),这个表达式告诉我们的有序表长度为F[k] -1时,可以将它分成F[K-1] -1和F[k-2] -1这两部分,也就是图中所示的一样,这样的话我们的mid = low +F[k-1] -1.
• 我们可以类比上面所述,每一个子段也可以采用此过程进行分割的
• 我们需要考虑到一个点,我们的有序列表的长度size可能不一定刚好等于F[k] -1;这个时候就需要考虑到增加原来的有序列表长度由size增至F[k] -1. 注意:k的值要能让F[k] -1的值恰好大于等于size即可,当然原有序列表的长度是从size+1处到F[k] -1的位置上都填充原有序列表的为size处的数字即可.

说了这么多,很难理解,我们通过代码来实现,假设我的有序列表为int[] arr = {1,8,10,89,1000,1234},来看代码:

代码实现

我们都知道黄金分割借助于斐波拉契来实现的首先我们来初始一组斐波拉契数列

static int maxSize = 20; //斐波拉契数列默认大小

   //创建一个斐波拉契数列 mid = left +F(k-1) -1;
public static int[] fiBo(){
    int[] fi = new int[maxSize];
    fi[0] = 1;
    fi[1] = 1;
    for (int i = 2; i <maxSize ; i++) {
        fi[i] = fi[i -1] + fi[i -2];
    }
    System.out.println(Arrays.toString(fi));
    return fi;
}

• 测试结果如下图

  
  测试结果.png

我们的第一步完成了,接下来我看查找的过程,代码如下:

/**
 *
 * @param arr 待查找的数组
 * @param findVal 要查找的数
 * @return 找到返回下标,没找到返回-1
 */
public static int fibSearch(int[] arr,int findVal){
    //变量的定义
    int left = 0; //左边索引
    int right =arr.length -1; //右边索引
    int k = 0; //斐波拉契分割数值的下标
    int mid = 0; //存放找到的mid值
    int[] f = fiBo(); //获取斐波拉契数列
    //循环处理来查找斐波拉契分割数值的下标所对应的值
    while (right > f[k] -1){
        k++;
    }
    //可能存在f[k]的值大于了arr的长度,我们需要扩容,并指向数组temp[]
    //不足的部分使用0来补齐
    int[] temp = Arrays.copyOf(arr, f[k]);
    //我们使用arr数组的最后的数来填充temp数组
    //如:temp={1,8,10,89,1000,1234,0,0,0}====>{1,8,10,89,1000,1234,1234,1234,1234}
    //right +1 = 1234
    for (int i = right +1; i <temp.length ; i++) {
        temp[i] = arr[right];
    }
    //来找我们的findVal,循环处理
    while (left <= right){
        mid = left + f[k -1] -1;
        if (findVal < temp[mid]){ //我们应该在数组的左边继续找
            right = mid -1;
            //说明:
            //1.我们数组的全部元数 = left左边 +right元素
            //2.因为我们的黄金分割点是 f[k] = f[k -1] + f[k -2]
            //3. 可以发现的,当前左边还有f[k -1]个元素,因此可以继续拆分f[k -1] = f[k -2] + f[k -3]等
            // 也就是说在f[k -1]的左边继续查找,即 k-- 即 mid = f[k - 1 -1] -1
            k --;
        }else if (findVal > temp[mid]){ //我们应该在数组的右边继续找
            left = mid +1;
            //说明:
            //1.我们数组的全部元数 = left左边 +right元素
            //2.因为我们的黄金分割点是 f[k] = f[k -1] + f[k -2]
            //3.可以发现的,当前右边还有f[k -2]个元素,因此可以继续拆分f[k -1] = f[k -3] + f[k -4]等
            //即在f[k -2]的右边继续查找 k -=2个元素,即 mid = f[k -1 -2] -1
            k -= 2;
        }else { //表示找到了
            //比较下,我们返回的最小的那个
            if (mid <= right){
                return mid;
            }
            return right;
        }
    }
    return -1;
}

这就是查找核心代码,注释很详细,再加上上面我们文字的解释,结合代码相信大家能明白,我们来看测试代码:

public static void main(String[] args) {

    int[] arr = {1,8,10,89,1000,1234};

    int indexResult = fibSearch(arr, 1234);
    System.out.println(indexResult);

}

• 测试结果如下图:

  
  斐波拉契测试结果.png

结果证明代码是没问题,那么关于黄金分割的学习就到这了...