查找--斐波那契查找（Java）
博客阐明
文章所波及的材料来自互联网整顿和集体总结，意在于集体学习和教训汇总，如有什么中央侵权，请分割自己删除，谢谢！
介绍
黄金分割点是指把一条线段宰割为两局部，使其中一部分与全长之比等于另一部分与这部分之比。取其前三位数字的近似值是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; }}感激
尚硅谷万能的网络
以及勤奋的本人