斐波那契查找算法（Fibonacci Search）是一种基于斐波那契数列的查找算法，用于在有序数组中进行查找操作。该算法使用黄金分割原理，将数组分割成两部分，并通过比较目标值与数组中间元素的大小来确定下一次查找的范围。
public static int fibonacciSearch(int[] arr, int key) { int n = arr.length; int fib2 = 0; // 第二个斐波那契数 int fib1 = 1; // 第一个斐波那契数 int fib = fib1 + fib2; // 找到大于等于数组长度的斐波那契数 while (fib < n) { fib2 = fib1; fib1 = fib; fib = fib1 + fib2; } int offset = -1; // 查找起始位置的偏移量 while (fib > 1) { int i = Math.min(offset + fib2, n - 1); if (arr[i] < key) { fib = fib1; fib1 = fib2; fib2 = fib - fib1; offset = i; } else if (arr[i] > key) { fib = fib2; fib1 = fib1 - fib2; fib2 = fib - fib1; } else { return i; } } if (fib1 == 1 && arr[offset + 1] == key) { return offset + 1; } return -1; // 如果未找到目标元素，返回-1 }
斐波那契查找算法的时间复杂度为O(log n)，其中n是数组的长度。该算法利用了斐波那契数列的性质，在查找过程中不断调整斐波那契数列的值来确定查找的范围，从而提高了查找效率。
