农的 根据菱波那契序列的特点对有序表分制 0.618法 菱波那契序列 1235813213455……f(m f(n+2)=f(m)+(n+1) 从20个数的数表中查找一个纪录 先找比较第13个,如果小,再比较第8个, 如果大比较后几个数的第5个 每次都比较位于这个数列的黄金分割点0.618处 比如123456789101112131415 16 查找15的位置2、静态查找表(cont’d) (2)有序表的查找 III.斐波那契查找： 根据斐波那契序列的特点对有序表分割 0.618法 斐波那契序列 1 2 3 5 8 13 21 34 55······f(n)······ f(n+2)=f(n)+f(n+1) 从20个数的数表中查找一个纪录 先找比较第13个，如果小，再比较第8个，···· 如果大 比较后几个数的第5个······ 每次都比较位于这个数列的黄金分割点0.618处 比如 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 查找15的位置