Fibonacci 查找的方法是根据Fibonacci 数列的特点对查找表进行分割。其查找表有一个特点就是: 查找表的长度等于某个Fibonacci 数值减 1 。即:
n = table.length , fn = fib(k) ; n = fn -1 ;
如果不满足这个条件,则不能使用Fibonacci 查找方法进行查找。使用 l , h , m ,表示待查找表的下界、上界 、 和分割位置, l = 0 , h = n -1 ,
取 m = l + f (n -1) -1 ;
如果 相等 ,则返回该位置 ;
如果 该值大于key , 则表示key在分割位置前,取 h = m ;
如果 该值小于key, 则表示key在分割位置后, 取 l = m ;
直到 l >= h 或者 f(n-1) = 0 ;
以下为一个Java版实现:
public static int fibSearch(int[] data, int key) { if (data == null || data.length == 0) { return -1; } int l = 0, h = data.length, m; int j = maxFibNum(h); int f1 = fib(j- 1), f2 = fib(j - 2); h--; while (l <= h && f1 > 0) { m = l + f1 -1; if (data[m] == key) { return m; } else if (data[m] > key) { h = m; f2 = f1 - f2; f1 = f1 - f2; } else { l = m; f2 = f1 - f2; f1 = f1 - f2; } } return -1; } public static int fib(int n) { int f0 = 0, f1 = 1, fn =1; if (n == 0) return f0; else if (n == 1) return f1; else if (n > 1) { for (int i = 2; i <= n; i++) { fn = f0 + f1; f0 = f1; f1 = fn; } return fn; } return -1; } public static int maxFibNum(int n){ // n 数据元素的长度 int f0 = 0, f1 = 1, fn =1; if (n == 0) return f0; else if (n == 1) return f1; else if (n > 1) { for (int i = 2; i <= n; i++) { fn = f0 + f1; if(fn - 1 == n) return i; f0 = f1; f1 = fn; } } return -1; } public static int[] DATA_COLLECTION = { 1, 2, 7, 24, 30, 45, 46, 78, 234, 567, 888, 987 }; public static void main(String[] args) { System.out.println(fibSearch(DATA_COLLECTION, 567)); }
个人感觉Fibonacci查找方法数鸡肋中的鸡肋,首先其效率不见得比二分查找好,其次就是对查找表的长度的要求,实际中很少会用到该查找方法。只是作为学习,了解其思想还是不错的。