和插值查找法一样,斐波那契查找(Fibonacci Search)算法也是有序表的一种查找方式,同样属于二分查找的一个优化,它是利用了黄金分割原理(斐波那契数列)来实现的。一般情况下斐波那契查找算法的速度比二分法要快的多,能有效减少查找循环的次数。改变了中间结点(mid)的位置,mid不再是中间或插值得到,而是位于黄金分割点附近,即mid=low+F(k-1)-1(F代表斐波那契数列)。
1、斐波那契查找(Fibonacci Search)算法介绍
用途:能在大量的数据中找到自己想找的元素,减少查找的循环的次数。
条件:斐波那契查找(Fibonacci Search)算法类似于二分查找法和插值查找,必须是有序列表。对于非有序序列,可以先进行排序后再使用插值查找算法查找。
原理:
- 对一个有序数列进行查找的时候,二分法(即折半查找)是利用中间值middle来一步步缩小搜索的范围,直至找到最终结果。时间复杂度:O(log(n))。
- 插值查找算法同二分法类似,唯独中间值middle的计算方式不一样,该middle值会尽可能的接近我们要查找的值,减少查找的次数,时间复杂度一样为 O(log(n))。
- 斐波那契查找(Fibonacci Search)算法和二分法及插值算法一样,不同的是middle值不再是中间或插值得到,而是位于黄金分割点附近,即mid=low+F(k-1)-1(F代表斐波那契数列)。
斐波那契数列:
斐波那契数列:即1,1,2,3,5,8,13…,从第三个数开始,后面的数都等于前两个数之和,而斐波那契查找就是利用的斐波那契数列来实现查找的。初始化的斐波那契数列最后一位要大于等于数组元素的size-1。
查找步骤:
假设表中有 n 个元素,查找过程为获取区间的下标 mid=low + fibonacci[k - 1] - 1 ,对 mid 的关键字与给定值的关键字比较:
- 如果与给定关键字相同,则查找成功,返回mid和high的最小值;
- 如果给定关键字大,向右查找并减小2个斐波那契区间;
- 如果给定关键字小,向左查找并减小1个斐波那契区间;
- 重复过程,直到找到关键字(成功)或区间为空集(失败)。
2、实现方式
2.1 实例1
import org.junit.Test;
import java.util.Arrays;
/**
* 斐波那契查找算法
*/
public class FibonacciSearch {
/**
* 有序的数组
*/
public int[] elements = new int[]{1, 16, 24, 35, 47, 59, 62, 73, 88, 99};
/**
* 对应的斐波拉契数组,数组的最大值>=elements.length-1
* 本例中elements.length-1==9,所以对应的fibonacci数组的最大值>=9, 取值为13
*/
public int[] fibonacci = new int[]{1, 1, 2, 3, 5, 8, 13};
@Test
public void test() {
System.out.println(fibonacciSearch(88));
}
/**
* 斐波那契查找的实现
*
* @param key 要查找的数据
* @return 查找到的索引, 或者-1 表示查找到
*/
public int fibonacciSearch(int key) {
//最小索引
int low = 0;
//最大索引
int high = elements.length - 1;
//不在范围内,直接返回-1
if (elements[low] > key || elements[high] < key) {
return -1;
}
int k = 0, i, mid;
/*计算high位于斐波那契数列的位置 */
//这里high为9,fibonacci[5]<9<fibonacci[6] ,取大的,即k=6
while (high > fibonacci[k]) {
k++;
}
/*扩展数组*/
//扩展原数组,长度扩展为fibonacci[k]=13,即多加了三个位置elements[10],elements[11],elements[12]
elements = Arrays.copyOf(elements, fibonacci[k]);
//为了保证数组的顺序,把扩展的值都设置为原始数组的最大值
for (i = high + 1; i < elements.length; i++) {
elements[i] = elements[high];
}
/*开始斐波那契查找*/
while (low <= high) {
System.out.println("------");
/* 计算当前分隔的下标索引,取的是黄金分割点 7-4-2-1-0 7-10*/
mid = low + fibonacci[k - 1] - 1;
/* 若查找记录小于当前分隔记录 */
if (key < elements[mid]) {
/* 最高下标调整到分隔下标mid-1处 */
high = mid - 1;
/* 斐波那契数列下标减一位 */
k = k - 1;
}
/* 若查找记录大于当前分隔记录 */
else if (key > elements[mid]) {
/* 最低下标调整到分隔下标mid+1处 */
low = mid + 1;
/* 斐波那契数列下标减两位 */
k = k - 2;
} else {
/* 若mid <= high则说明mid即为查找到的位置,返回mid */
/* 若mid>high说明是补全数值,返回high */
return Math.min(mid, high);
}
}
return -1;
}
}
2.2 实例2
import java.util.Arrays;
/**
* 斐波那契查找算法
*/
public class FibonacciSearch {
public static int Maxsize = 20;
public static void main(String[] args) {
int[] arr = {1, 3, 5, 7, 9, 12, 15};
int val = findVal(arr, 12);
System.out.println(val);
}
//用函数定义一个斐波那契数列
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 findVal(int[] arr, int key) {
int low = 0;
int high = arr.length - 1;
int f[] = fib();// 调用的斐波那契数列
int k = 0;//斐波那契数列所以
int mid = 0;
while (high > f[k]) {
k++;
}
// 因为斐波那契数组的f[k]值可能大于arr数组的长度,
// 因此我们要使用Arrays类,构造一个新的数组,并指向arr[], 不足的部分会使用0填充
int[] temp = Arrays.copyOf(arr, f[k]);
// 实际上需求用arr最后的值来进行补充
for (int i = high + 1; i < temp.length; i++) {
temp[i] = arr[high];
}
// 使用while循环,找到数key, 只要这个条件满足,就可以找
while (low <= high) {
System.out.println("---");
//中间下标
mid = low + f[k - 1] - 1;
if (key < temp[mid]) {
// 要找的数小于中间值,说明在数组的左边 fibIndex--;
high = mid - 1;
k--;
} else if (key > temp[mid]) {
// 要找的值大于中间值说明在数组的右边
// fibonacci[fibIndex]=fibonacci[fibIndex-1]+fibonacci[fibIndex-2];
// fibonacci[fibIndex-1] 为数组左边的值 fibonacci[fibIndex-2]为数组右边的值
low = mid + 1;
k -= 2;
} else {
// 注意:这里要进行判断返回时是哪个下标
// 如果mid<=high,返回mid; 如果mid>high,返回high;
if (mid <= high) {
return mid;
} else {
return high;
}
}
}
return -1;
}
}
3、总结
如上图,斐波那契查找的特点就是左侧半区范围大于右侧半区范围。如果要查找的记录在mid右侧,则左侧的数据都不用再判断了,不断反复进行下去,对处于右侧当中的大部分数据,其工作效率要高一些。 所以尽管斐波那契查找的时间复杂也为O(logn),但就平均性能来说,斐波那契查找要优于二分查找。可惜如果是最坏情况,比如这里key=1,那么始终都处于左侧长半区在查找,则查找效率要低于二分查找。
还有比较关键的一点,二分查找是进行加法与除法运算(mid=(low+high)/2),插值查找进行复杂的四则运算(mid=low+(highlow) * (key-a[low])/(a[high]-a[low])),而斐波那契查找只是最简单加减法运算(mid=low+F[k-1]-1),在海量数据的查找过程中,这种细微的差别可能会影响最终的查找效率,但是斐波那契额查找同样需要额外的空间。
评论区