1. 构建获取斐波那契数列值的一个函数
function getFibonacciListValue (num) { if(num===0){ return 0 }else if(num===1){ return 1 }else{ return getFibonacciListValue(num-2) + getFibonacciListValue(num-1) } } let fib = getFibonacciListValue(10) console.log(fib)2. 构建斐波那契查找函数
let data = [1,16,24,35,47,59,62,73,88,99] //10 function fibonacciSearch (list,item) { let low = 0 let height = list.length-1 //9 let k = 0 let mid while(height>getFibonacciListValue (k)-1){ k++ }//k=7 for(let i = height;i<=getFibonacciListValue(k)-1;i++){ list[i] = list[height] }//extlength console.log(list) while(low<=height){ mid = low + getFibonacciListValue(k-1)-1 let guess = list[mid] if(guess===item){ if(mid>height){ return height }else{ return mid } }else if(guess<item){ low = mid+1 k=k-2 }else{ height = mid-1 k=k-1 } } return null } let position = fibonacciSearch (data,99) console.log(position)3. 要点解析
斐波那契数列上的值，实际上表示要进行查找的列表的长度。而中位索引mid的值根据斐波那契数列得出（ mid = low +getFibonacciListValue(k-1)-1）
例子推导： 1.由于查找列表data 的长度为10，处于斐波那契数列索引6与7之间，getFibonacciListValue(6)=8 getFibonacciListValue(7)=13，8<10<13。 2.这里将数组长度视为13，为了保持数组长度一致，于是延长数组3个位并用最高位索引的值 (99)代替，10+3=13。用k保存斐波那契数列的索引，所以k=7。 3.由斐波那契数列可以知道，当数组长度为13时，用黄金比例分割可以将数组分成2部分，第一部 份长度为8，第二部分长度为5。由此可以得出中位索引mid为getFibonacciListValue(k-1)-1，即 8-1=7 4.当mid索引上的值比查找值大的时候，除了height=mid-1外，还需k=k-1,因为需要知道剩下的， 仍需查找的数组长度是多少。当长度为13的数组分成2部分找，发现查找的值可能在长度为8第一 部分中，于是需要把索引k定位到表示长度为8的索引上，所以此时k=k-1=7-1=6 当mid索引上的值比查找值小的时候，除了low=mid+1外，还需k=k-2，同理当长度为13的数组分 成2部分找，发现查找的值可能在长度为5第二部分中，于是需要把索引k定位到表示长度为5的索引 上，所以此时k=k-2=7-2=5 5.当找到相同的值并把索引位置返回时，需要判断mid是否大于height，如果大于则以height为索引 返回。因为一开始我们已经将数组延长到与斐波那契数列值相同，这里的例子是把长度由10延长到 13，这样才能进行黄金比例分割。所以在例子中发生这种情况时返回的height索引应为9
核心本质：mid值由斐波那契数列推导而出（黄金分割比例）
4. 算法的优势和弱势
优势：mid值的运算公式是简单加减法，公式的运算上比2分查找还要简单 弱势：因为本质是黄金比例分割，因此分割完成后会具有数据多的部分和数据少的部分， 如果要查找的数值一直落在数据多的那一部分中，会导致查找时间变长。当发生这种情况时花费的时间就会比2分查找花费的时间多。同时斐波那契查找与2分查找一样只针对有序列表进行查找
