斐波那契查找算法(思路分析)

斐波那契查找算法又称为黄金分割查找法

斐波那契查找算法的基本介绍:

首先我们先来了解什么是黄金分割?

黄金分割点就是指把一条线分割为两部分,其中一部分与全长之比等于另一部分与这部分之比,这个比值取其前三位的近似值是0.618,由于按照此比例设计的造型十分美丽,因此也称之为黄金分割,也称之为中外比,这是一个神奇的数字,总是会带来意想不到的效果
- 而我们的斐波那契数列{1,1,2,3,5,8,13,21,34,55}, 我们可以发现越往后斐波那契数列的两个相邻数的比例会无限的接近于黄金分割值(0.618)

斐波那契查找算法的原理:

斐波那契查找算法的原理和折半查找和插值查找算法很是相似,仅仅是改变了中间结点mid的位置,mid不再是中间或者插值,而是位于黄金分割点附近,即mid = low + f[k - 1] - 1 —> 这里的f代表的是斐波那契数列

那么上面这个公式中f[k - 1] - 1是一个什么? 我们如何理解?

对f[k - 1] - 1的理解:

由斐波那契数列f[k] = f[k - 1] + f[k - 2] 可以推导出 , f[k] - 1 = (f[k - 1] - 1) +(f[k - 2] - 1) + 1,那么推导出这个公式又有什么作用?

该公式说明: 只要顺序表的长度为f[k] - 1 ,则我们就可以将顺序表分为三部分: 也就是f[k - 1] - 1, f[k - 2] - 1 和 1,一共是三部分,那么mid的位置就会是mid = low + f[k - 1] -1

我们这里通过一个图解来进行一个深入的理解:

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Ooqs1x91-1662108364873)(E:\非凡英才\数据结构(java)]\数据结构图解\图解理解斐波那契查找算法.png)

并且我们仔细研究之后可以发现我们的f[k] - 1可以分为 f[k - 1] - 1和f[k - 2] - 1,这个时候,如果是下一次循环的执行的时候要么是向左执行,要么是向右执行,如果是向左执行,那么数组的长度就会从f[k] - 1变成 f[k - 1] -1,如果是向右执行,数组的长度就会从f[k] - 1变成f[k - 2] - 1, 这个时候我们的f[k - 1] - 1和 f[k - 2] - 1又符合我们的斐波那契查找算法中数组的长度,这个时候就可以一直执行下去了
- 但是注意: 我们最开始的时候数组的长度不一定刚好等于f[k] - 1,所以我们就需要编写一个斐波那契数列,然后去数列中找,找到斐波那契数列中的第一个大于等于我们数组长度 + 1的数值,这里为什么要找大于数组长度加1? 因为这时候其实就是要求我们的数组长度 = f[k] - 1,也就是我们的数组长度 + 1 = f[k] ,如果不等于,这个时候我们就进行一个数组扩容(直接使用Arrays工具类中的copyOf)方法),但是我们数组扩容之后数组的扩容部分是默认值,也就是0,这个时候显然是不行的,这个时候我们要将扩容部分的值都修改成我们的原数组中的最后一个值的大小(也就是我们的原数组中最大的值)

思路分析:(这里我们使用非递归来实现)

首先我们这里是斐波那契查找算法,那么我们肯定是要先创建一个斐波那契数列,也就是创建一个数组,数组中存放我们的斐波那契数列的值,但是这个时候我们的这个数组要创建多大,这个就是要视情况而定了,具体和我们查找的数组有关,因为我们在斐波那契数组中肯定是要找到一个比我们的的查找数组长度长的或者最起码相等的一个值

我们创建好了斐波那契数组之后,我们要定义一些临时变量,用于我们进行查找,我们的斐波那契查找也是用了二分的思想,只是我们的斐波那契查找的时候不是对半分而已, 所以我们的斐波那契查找算法中也是要定义一个left(初始为0) ,定义一个right(初始为arr.length - 1),定义一个mid,定义一个int型的数组f(就是我们的斐波那契数组),然后再定义一个变量k(来表示我们找到的斐波那契数组中的第一个比查找数组长度长的值的下标)
- 那么我们下面就正式的进入到我们的斐波那契查找的过程中了,这个时候我们要查找肯定要先找到我们的mid的位置,要找到mid的位置,就必须先找到斐波那契数组中第一个比数组长度大的值,那么我们如何找到这个值?
  - 很简单: 我们只需要使用一个while循环就可以了,我们判断只要arr.length > f[k] - 1,那么就是代表还没有找到,就让我们的k值加一,也就是k后移,等到退出循环的时候,这个时候的k对应的f[k] 肯定就是大于我们的数组长度的了(我们的f[k] - 1 肯定是大于或者等于数组的长度的)
    - 那么找到了这个f[k] - 1的值之后,我们就要让我们的数组进行一个扩容,扩容到长度为f[k] - 1即可,这个时候我们直接调用Arrays工具类中的copyOf()方法即可,扩容之后我们再通过一次循环将我们的扩容位置的数值全部改为我们的原数组中的最后一个位置的数值(也就是我们的原数组中的最大值) --> 注意: 如果这个时候我们没有进行数组扩容,那么我们计算出的mid的值如果是在右边,这个时候就有可能会出现数组下标越界,也就是我们的mid跑到了我们的high之外的位置,所以我们为了避免这个情况的发生,这个时候我们就要对数组进行一个扩容
      - 然后直接计算我们的mid即可,我们的mid的值的计算我们就直接带入公式即可
        mid = low + f[k - 1] - 1;
        然后使用arr[mid]和我们的目标值进行一个比较,如果我们的目标值大,则进行low = mid + 1;并且让我们的k -= 2, 如果我们的目标值小,则进行high = mid - 1;,并且让我们的k -= 1,如果我们的目标值和arr[mid]相等,这个时候我们也不要着急返回mid的值,因为这个时候我们的mid的位置可能是指向了扩容的位置,所以我们就要在返回mid之前做一步判断,这个时候我们判断,如果正常我们找到的mid的时候mid 都会是小于等于high的,我们就可以直接return mid,但是有一种情况就是我们的mid值是大于我们的high的,这个时候就是我们的mid直接跳过了high的值,到了扩容的部分,这个时候我们就不应该返回mid,而是应该返回一个high
        如果最终while循环执行完之后都没有找到我们的和目标值大小相等的mid位置,这个时候我们就直接return -1就可以了

算法核心:

其实算法的核心就是开始的时候要将我们的待查找数组扩容为一个符合斐波那契规范的长度, 我们的斐波那契数列中的值是固定的, 第一项和第二项都是1, 然后之后的每项的值都等于前两项的和, 所以说我们的斐波那契数列的值其实都是固定的, 我们的待查找数组要使用斐波那契查找算法来完成查找的工作, 那么肯定就要满足我们的待查找数组的长度是我们的斐波那契数列中的某个值,那么这个时候问题就来了, 我们的数组长度不一定就是斐波那契数列中的某个值的大小, 所以我们在使用斐波那契查找算法的时候就要将待查找数组长度扩容为斐波那契数列中某个比数组长度大的值的长度, 那么首先我们就是要创建一个斐波那契数列, 然后用作找到一个斐波那契数列中的第一个比待查找数组长度大的值

补充:

上面的思路分析中high = mid -1 之后执行k -= 1是因为这个时候我们是向左查找,而我们的右边是长的部分,这个时候长的部分就是f[k - 1] - 1,所以我们的k下次计算的时候mid就应该是low + f[(k - 1) - 1] - 1,所以这个时候相对于我们的开始的f[k] - 1来讲我们肯定是要执行一个 k -= 1,那么相应的如果是向右边查找,这个时候就应该是k - 2,因为右边第一次短的部分,也就是f[k - 2] - 1,那么这个时候我们要在总长度为f[k - 2] - 1的数组中找到mid的位置,这个时候mid的公式自然就是 f [(k - 2) - 1] - 1,这个时候相对于开始的f[ k ] - 1长度来讲我们肯定是要执行一个k - 2

我们斐波那契查找算法的时间复杂度也是O(logn),但是一般情况下我们的斐波那契查找算法的效率还是要高于折半查找的