本系列博客习题来自《算法(第四版)》，算是本人的读书笔记，如果有人在读这本书的，欢迎大家多多交流。为了方便讨论，本人新建了一个微信群(算法交流)，想要加入的，请添加我的微信号：zhujinhui207407 谢谢。另外，本人的个人博客 http://www.kyson.cn 也在不停的更新中，欢迎一起讨论
知识点
- 仅用加减实现的二分查找(斐波那契搜索)
- 斐波那契数列的使用
题目
1.4.22 仅用加减实现的二分查找（Mihai Patrascu）。编写一个程序，给定一个含有 N 个不同 int 值的按照升序排列的数组，判断它是否含有给定的整数。只能使用加法和减法以及常数的额外内存空间。程序的运行时间在最坏情况下应该和 logN 成正比。提示：用斐波那契数代替2的幂（二分法）进行查找。用两个变量保存Fk和Fk-1并在[i,i+Fk]之间查找。在每一步中，使用减法计算Fk-2，检查i+Fk-2处的元素，并根据结果将搜索范围变为[i,i+Fk-2]或是[i+Fk-2,i+Fk-2+Fk-1]。
1.4.22 Binary search with only addition and subtraction. [Mihai Patrascu] Write a program that, given an array of N distinct int values in ascending order, determines whether a given integer is in the array. You may use only additions and subtractions and a constant amount of extra memory. The running time of your program should be proportional to log N in the worst case.
Answer: Instead of searching based on powers of two (binary search), use Fibonacci numbers (which also grow exponentially). Maintain the current search range to be the interval [i, i + F k] and keep F k and F k–1 in two variables. At each step compute Fk–2 via subtraction, check element i + Fk–2 , and update the current range to either [i, i + Fk–2] or[i+Fk–2,i+Fk–2 +Fk–1].
分析
我们看题目中有个人名Mihai Patrascu，这个人是谁呢，我们先看一下知乎里的高票回答：
有哪些人堪称「神人」，却不为大众所知？
里面说到：
算法界的天才人物Mihai Pătraşcu 于2012年Presburger奖（青年理论计算科学顶级奖），在数据结构下限等基础领域有突破贡献。信息学奥林匹克IOI界的名人，获得两次金牌，一次银牌。MIT博士，师从神童教授Erik Demaine（没读中小学12岁上大学，4年本科，1年master，1年phd，20岁时博士毕业）
他在麻省的介绍：http://people.csail.mit.edu/mip/
维基百科的介绍：https://en.wikipedia.org/wiki/Mihai_P%C4%83tra%C8%99cu
所以这个仅用加减实现的二分查找的算法是Mihai Pătraşcu 提出的?(我也不确定)。那有了二分法搜索为什么又提出斐波那契搜索呢，是否斐波那契搜索比二分法搜索，相信很多做完此题的读者都会有这个疑问，这里我在Stack Overflow帮大家找到了相应的问答，供大家参考：
Is fibonacci search faster than binary search?
大概的意思就是，斐波那契查找的时间复杂度还是O(log2n )，但是与折半查找相比，对磁盘的操作更省力，因此，斐波那契查找的运行时间理论上比折半查找小。最后我们对斐波那契搜索做个更加详细的说明：
斐波那契搜索就是在二分查找的基础上根据斐波那契数列进行分割的。在斐波那契数列找一个等于略大于查找表中元素个数的数F[n]，将原查找表扩展为长度为Fn，完成后进行斐波那契分割，即F[n]个元素分割为前半部分F[n-1]个元素，后半部分F[n-2]个元素，找出要查找的元素在那一部分并递归，直到找到。
答案
public class FibonacciSearch {
private final int FI_SIZE = 20;
public int fbSearch(int[] array, int target) {
if (array == null || array.length == 0) {
return -1;
} else {
int length = array.length;
// 制造一个长度为10的斐波数列
int[] fb = makeFbArray(FI_SIZE);
int k = 0;
// 找出数组的长度在斐波数列（减1）中的位置，将决定如何拆分
while (length > fb[k] - 1) {
k++;
}
// 构造一个长度为fb[k] - 1的新数列
int[] temp = Arrays.copyOf(array, fb[k] - 1);
for (int i = length; i < temp.length; i++) {
if (i >= length) {
temp[i] = array[length - 1];
}
}
int low = 0;
int high = array.length - 1;
while (low <= high) {
int middle = low + fb[k - 1] - 1;
if (temp[middle] > target) {
high = middle - 1;
k = k - 1;
} else if (temp[middle] < target) {
low = middle + 1;
k = k - 2;
} else {
if (middle <= high) {
// 若相等则说明mid即为查找到的位置
return middle;
} else {
// middle的值已经大于hight,进入扩展数组的填充部分,
//即最后一个数就是要查找的数。
return high;
}
}
}
return -1;
}
}
public static int[] makeFbArray(int length) {
int[] array = null;
if (length > 2) {
array = new int[length];
array[0] = 1;
array[1] = 1;
for (int i = 2; i < length; i++) {
array[i] = array[i - 1] + array[i - 2];
}
}
return array;
}
}
测试用例
public static void main(String[] args) {
int[] array = {1, 5, 15, 22, 25, 31, 39, 42, 47, 49, 59, 68, 88, 88,
88, 88, 88};
FibonacciSearch search = new FibonacciSearch();
System.out.println("result: " + search.fbSearch(array, 31));
}
代码索引
广告
我的首款个人开发的APP壁纸宝贝上线了，欢迎大家下载。
