文章所涉及的资料来自互联网整理和个人总结,意在于个人学习和经验汇总,如有什么地方侵权,请联系本人删除,谢谢!
黄金分割点是指把一条线段分割为两部分,使其中一部分与全长之比等于另一部分与这部分之比。取其前三位数字的近似值是0.618。
斐波那契数列{1, 1, 2, 3, 5, 8, 13, 21, 34, 55 } 发现斐波那契数列的两个相邻数 的比例,无限接近 黄金分割值0.618
利用 斐波那契数列 的特性来查找mid
package cn.guizimo.search; import java.util.Arrays; /** * @author guizimo * @date 2020/7/23 10:06 下午 */ public class FibonacciSearch { public static int maxSize = 20; public static void main(String[] args) { int[] arr = {1, 8, 10, 89, 100, 1000}; System.out.println(fibSearch(arr,8)); } //斐波那契数列 public static int[] fib() { int[] f = new int[maxSize]; f[0] = 1; f[1] = 1; for (int i = 2; i < maxSize; i++) { f[i] = f[i - 1] + f[i - 2]; } return f; } public static int fibSearch(int[] a, int key) { int low = 0; int high = a.length - 1; int k = 0; int mid = 0; int f[] = fib(); while (high > f[k] - 1) { k++; } int[] temp = Arrays.copyOf(a, f[k]); for (int i = high + 1; i < temp.length; i++) { temp[i] = a[high]; } while (low <= high) { mid = low + f[k - 1] - 1; if (key < temp[mid]) { high = mid - 1; k--; } else if (key > temp[mid]) { low = mid + 1; k -= 2; } else { if (mid <= high) { return mid; } else { return high; } } } return -1; } }
尚硅谷
万能的网络
以及勤劳的自己
很遗憾的说,推酷将在这个月底关闭。人生海海,几度秋凉,感谢那些有你的时光。
原文 https://segmentfault.com/a/1190000023356044