参考文档：https://zq99299.github.io/dsalg-tutorial/dsalg-java-hsp/08/04.html#%E5%9F%BA%E6%9C%AC%E4%BB%8B%E7%BB%8D

思路

斐波那契查找是二分查找的升级方式。mid的查找满足黄金比例（斐波那契数列，即后一项等于前两项相加），如下图：F(n) = F(n-1) + F(n-2)

image.png

步骤

参考https://zhuanlan.zhihu.com/p/106883697

  • 构建斐波那契数列；
  • 计算数组长度对应的斐波那契数列元素个数；
  • 对数组进行填充；
  • 循环进行区间分割，查找中间值；
  • 判断中间值和目标值的关系，确定更新策略；