斐波那契查找

李现实

我想问下我看不懂这个画红色怎么找到这个中间值的。斐波那契小甲鱼讲的好模糊。。

lei1996

栗子解析
数组arr，大小为12，斐波那契数组f，设定大小为10，待查找数字为10
1.首先在f中找到略大于arr大小12的数字，是13，然后把arr的大小扩充为13，末尾填充12
2.然后f[k]=f[k-1]+f[k-2]即13 = 8+5，然后假定将arr划分为两部分，第一部分为前八个元素即{1,2,3,4,5,6,7,8}后一部分为5个元素{9,10,11,12,12}
3.比较第八个元素（栗子中为8）与目标值（10）的，如果第八个元素大于目标值则目标值在第一部分内，而栗子中小于目标值，则目标值在第二部分中，记录第二部分的起点索引，整体大小为5，再带到2步骤中，f[k]=f[k-1]+f[k-2]即5=3+2，依次递归

lei1996

最好结合代码看，能加深理解https://www.cnblogs.com/yysbolg/p/11603605.html