您现在的位置是：首页 > 后台技术 > 数据结构与算法数据结构与算法

斐波拉契（黄金分割）查找算法(图文)

第十三双眼睛2023-10-18【数据结构与算法】人已围观

简介斐波拉契（黄金分割）查找算法

斐波拉契（黄金分割）查找算法

package com.xingchen.day007;
import java.util.Arrays;
public class FibonacciSearch {
public static int maxSize = 20;
public static void main(String[] args) {
int[] arr = {1,8,10,89,1000,1234};
// 因为要用到斐波那契数列,这里构造一个
int i = fibSearch(arr, 89);
System.out.println(i);
}
public static int fibSearch(int[] arr, int key) {
int low = 0;
int high = arr.length - 1;
int k = 0;//斐波那契数值分割下标
int mid = 0;
int f[] = feibo();
// 获取斐波那契分割数值下标
while (high > f[k] - 1) {
k++;
}
// 因为f[k]得值可能大于数组得长度，因此需要构造一个数组
int[] temp = Arrays.copyOf(arr, f[k]);
//还需要用arr数据最后得值填充temp
for (int i = high + 1; i< temp.length;i++) {
temp[i] = arr[high];
}
// 使用while循环处理,来找到我们得数
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;
}
public static int[] feibo() {
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;
}
}

Tags：

很赞哦！ ()

上一篇：插值查找(图文)

下一篇：哈希表(图文)