斐波那契数列片段:
有序数组:
数组长度11,斐波那契数列大于11的最小值是13,将数组扩容到长度为13,增加的两个位置存储的值为数组值的最大值99:
此时k=7,f(k)=13,f(k-1)=8,f(k-2)=5,将数组分成两个部分,左边长度是f(k-1),右边长度是f(k-2),我们要查找的位置下标是f(k-1)-1:
public class FibonacciSearch {
public static int search(int[] arr, int key) {
if (arr == null || arr.length == 0)
return -1;
// pos是我们要查找的位置,类似折半查找的mid,k是斐波那契数列的位置下标
int low = 0, high = arr.length - 1, pos, k = 0, len = arr.length;
if (key < arr[low] || key > arr[high])
return -1;
if (len == 1)
return arr[0] == key ? 0 : -1;
// 数组长度对应的斐波那契数列的下标
while (len > f(k))
k++;
int[] arr1;
int len1 = f(k);
if (len < len1) { // 需要将数组扩容至长度为f(k)
arr1 = new int[len1];
System.arraycopy(arr, low, arr1, low, len);
for (int i = len; i < len1 - 1; i++)
arr1[i] = arr1[high];
} else {
arr1 = arr;
}
while (low <= high) {
if (k < 2) { // 斐波那契数列下标小于2时需要特殊处理
pos = low + f(k) - 1;
} else {
pos = low + f(k - 1) - 1;
}
if (key < arr1[pos]) {
high = pos - 1;
k -= 1;
} else if (key > arr1[pos]) {
low = pos + 1;
k -= 2;
} else {
// 如果数组进行了扩容,可能出现pos > len - 1的情况
return Math.min(pos, len - 1);
}
}
return -1;
}
public static int f(int i) {
if (i < 0) {
throw new IllegalArgumentException();
}
if (i < 2) {
return i;
}
return f(i - 2) + f(i - 1);
}
public static void main(String[] args) {
testCase5();
}
public static void testCase() {
int[] arr = {0, 1, 16, 24, 35, 47, 59, 62, 73, 88, 99};
int key = 101;
System.out.println(search(arr, key));
}
public static void testCase1() {
int[] arr = {0, 1, 16, 24, 35, 47, 59, 62, 73, 88, 99};
int key = -1;
System.out.println(search(arr, key));
}
public static void testCase2() {
int[] arr = {0, 1, 16, 24, 35, 47, 59, 62, 73, 88, 99};
int key = 36;
System.out.println(search(arr, key));
}
public static void testCase3() {
int[] arr = {1};
int key = 1;
System.out.println(search(arr, key));
}
public static void testCase4() {
int[] arr = {1, 2};
int key = 2;
System.out.println(search(arr, key));
}
public static void testCase5() {
int[] arr = {0, 1, 16, 24, 35, 47, 59, 62, 73, 88, 99};
for (int i = 0; i < arr.length; i++) {
System.out.println(search(arr, arr[i]));
}
}
}
斐波那契查找除了数组自身的查找开销,还有斐波那契数列的构建开销和数组扩容的开销。个人感觉不是太实用。



