Java版的数据结构和算法(二)

PS:本文系转载文章,阅读原文可读性会更好,文章末尾有原文链接

ps:本篇文章写斐波那契查找算法和数组、链表、树的存储方式

1、斐波那契查找算法

斐波那契数列,又称黄金分割数列,指的是这样一个数列:1、1、2、3、5、8、13、21、34、……;在数学上,斐波那契数列以如下被以递推的方法定义:F(0)=0,F(1)=1, F(n)=F(n - 1)+F(n - 2)(n ≥ 2),这里有一个黄金分割点的概念:指把一条线段分割为两部分,使其中一部分与全长之比等于另一部分与这部分之比,取其前三位数字的近似值是0.618;斐波那契数列中,两个相邻数的比例是无限接近与黄金分割值0.618。

“把一条线段分割为两部分,使其中一部分与全长之比等于另一部分与这部分之比,取其前三位数字的近似值是0.618” 这句话是什么意思呢?我来拿斐波那契数列里面的3个数(13、21 和 34)来举个例子,假设有一条绳子34米并把这条绳子命名为A,把A分成两段,一段是13米并命名为A1,另一段是21米并命名为A2;这个时候计算A1的长度除以A2的长度,约等于0.619;计算A2的长度除以A的长度,约等于0.617;这个时候A1/A2 是不是差不多等于A2/A,这回该理解蓝色的那一句话的意思了吧。

斐波那契查找算法与二分查找算法很类似,只是在于 mid 的计算不一样;

(1)在二分查找算法中,mid = (0 + array.length) / 2。

(2)在斐波那契查找算法中,我们要搞明白几个变量,那就是mid、low、high、F(k-1)-1,其中 mid=low+F(k-1)-1,low 表示什么呢?它表示一开始一个数列区间中最左边的下标,比如数组 arr={1,2,3,4,6},那么 low 一开始就是数组元素1的下标,也就是0;high 表示一开始一个数列区间中最右边的下标,比如数组 arr={1,2,3,4,5,6},那么 low 一开始就是数组元素6的下标,也就是5;mid 表示[low,high]之间的一个值;由斐波那契数列计算公式 F(k) = F(k-1) + F(k-2) 得到 F(k)-1 = (F(k-1) - 1) + (F(k-2) - 1) + 1,这时候把 F(k)-1 看做一根线总长名叫A,把 F(k-1) - 1 看做是 A 的一部分并命名为 A1,把 1 看做是 A 的一部分并命名为 A2,也就是表示1个数,那便是 mid,把 F(k-2) - 1 看做是 A 的一部分并命名为 A3,所以 mid 即表示[low,high]之间的一个值,也表示 F(k-1)-1 中的一个数。

我画个图来表示

图片

图1

好,我们举个例子,注意斐波那契数查找算法适合在有序的数列进行查找,这里有斐波那契数组 f={1,1,2,3,5,8,......},待查找的数组 arr={1,2,3,4,5,6},假设我们从 arr 数组中查找元素6的下标;

算法思路分析一把:

(1)拿到斐波那契数组 f 。

(2)判断数组 arr 的长度是不是斐波那契数组 f 中的一个元素,显然不是,arr 的长度在斐波那契数组 f 中是大于5而小于8,那么我们就把数组 arr 复制到一个长度为8的数组 temp 中,复制完成后 temp={1,2,3,4,5,6,0,0},我们把 temp 中为0的元素赋值数组 arr 的最大值6,赋值完成后 temp={1,2,3,4,5,6,6,6} 。

(3)判断 low 是否大于 high,如果大于就返回 -1,表示没有找到;low=0,high=arr.length=6,显然不是,程序往下走。

(4)计算 mid ,mid = low + f[k - 1] - 1,数组 temp 的长度是8,8在数组 f 的下标是5,所以k = 5,mid=0 + f[4] - 1=4 。

(5)判断查找值是否小于 temp[mid],如果成立,那么 high=mid-1,k--,这里为什么是 k--,我们再把 f[k - 1] - 1 这段(看图1理解)分成 f[(k -1) -1] -1 、mid 和 f[(k -2) -1] -1,所以新的 k 就等于 k-1,也就是 k--;判断查找值是否大于 temp[mid],如果成立,那么 low = mid + 1,k=k-2,这里为什么是 k=k-2,f[k -2] -1 分成 f[k -3] -1 、mid和 f[k -4] -1 这3部分,也就是 f[(k -2)-1] -1 、mid 和 f[(k -2)-2] -1,所以新的 k 就等于 k-2;判断查找值是否等于 temp[mid],如果成立,那么再如果 mid <= high,就返回 mid ,如果 mid > high ,就返回 high 。

(6)判断查找值是否大于 temp[4],显然成立,重新计算 k 和 low,k = 4 - 2 = 2,low = mid + 1 = 4 + 1 = 5 。

(7)重新计算 mid,mid = low + f[k - 1] - 1 = 5 + 1 - 1 = 5 。

(8)判断查找值是否等于 temp[5],显然成立,又如果 mid <= high,所以返回 mid 。

代码实现一把:

public class Test {

private static int maxSize = 100;
private static int[] fib() {

int[] f = new int[maxSize];
f[0] = 1;
f[1] = 1;
for (int i = 2; i <= maxSize - 1; i++) {
  f[i] = f[i - 1] + f[i - 2];
}
return f;

}

public static int fibSearch(int[] arr, int findVal) {

return fibSearch(arr, 0, arr.length - 1, findVal);

}

public static int fibSearch(int[] arr, int low, int high, int findVal) {

if (arr == null || arr.length <= 0)
  return -1;
int k = 0; // 表示斐波那契数列的下标
int[] f = fib(); // 获取斐波那契数组
int mid = 0;

// 获取斐波那契分割数值,比如在这个demo中,
// 判断数组 arr 的长度是不是斐波那契数组 f 中的一个元素,显然不是,
// arr 的长度在斐波那契数组 f 中是大于5而小于8,
// 那么我们就把数组 arr 复制到一个长度为8的数组 temp 中
// 8 在斐波那契数组 f 中的下标是5,所以k=5
while (high > f[k] - 1) {
  k++;
}
// 如果 f[k] > arr.length ,那么就将 arr 所有元素赋值给数组 temp
// 比如在这个demo中,temp={1,2,3,4,5,6,0,0}
int[] temp = Arrays.copyOf(arr, f[k]);

// 把扩容多出来的数赋予原来arr的最后一个数据
// 比如在这个demo中,将temp[6] = arr[5],temp[7] = arr[5]
for (int i = high + 1; i < temp.length; i++) {
  temp[i] = arr[high];
}

while (low <= high) {
  mid = low + f[k - 1] - 1;
  if (findVal < temp[mid]) {
    high = mid - 1;
    k--;
  } else if (findVal > temp[mid]) {
    low = mid + 1;
    k -= 2;
  } else {
    if (mid <= high) {
      return mid;
    } else {
      return high;
    }
  }
}
return -1;

}

public static void main(String[] args) {

int[] arr = { 1, 2, 3, 4, 5, 6 };
int resultIndex = fibSearch(arr, 6);
System.out.println(resultIndex);

}
}

你可能感兴趣的