本系列博客習(xí)題來(lái)自《算法(第四版)》悦析，算是本人的讀書(shū)筆記，如果有人在讀這本書(shū)的司光，歡迎大家多多交流琅坡。為了方便討論，本人新建了一個(gè)微信群(算法交流)残家，想要加入的榆俺，請(qǐng)?zhí)砑游业奈⑿盘?hào)：zhujinhui207407 謝謝。另外坞淮，本人的個(gè)人博客 http://www.kyson.cn 也在不停的更新中茴晋，歡迎一起討論
知識(shí)點(diǎn)
- 僅用加減實(shí)現(xiàn)的二分查找(斐波那契搜索)
- 斐波那契數(shù)列的使用
題目
1.4.22 僅用加減實(shí)現(xiàn)的二分查找（Mihai Patrascu）。編寫(xiě)一個(gè)程序碾盐，給定一個(gè)含有 N 個(gè)不同 int 值的按照升序排列的數(shù)組晃跺，判斷它是否含有給定的整數(shù)揩局。只能使用加法和減法以及常數(shù)的額外內(nèi)存空間毫玖。程序的運(yùn)行時(shí)間在最壞情況下應(yīng)該和 logN 成正比。提示：用斐波那契數(shù)代替2的冪（二分法）進(jìn)行查找凌盯。用兩個(gè)變量保存Fk和Fk-1并在[i,i+Fk]之間查找付枫。在每一步中，使用減法計(jì)算Fk-2驰怎，檢查i+Fk-2處的元素阐滩，并根據(jù)結(jié)果將搜索范圍變?yōu)閇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].
分析
我們看題目中有個(gè)人名Mihai Patrascu县忌，這個(gè)人是誰(shuí)呢掂榔，我們先看一下知乎里的高票回答：
有哪些人堪稱「神人」，卻不為大眾所知症杏？
里面說(shuō)到：
算法界的天才人物Mihai P?tra?cu 于2012年P(guān)resburger獎(jiǎng)（青年理論計(jì)算科學(xué)頂級(jí)獎(jiǎng)）装获，在數(shù)據(jù)結(jié)構(gòu)下限等基礎(chǔ)領(lǐng)域有突破貢獻(xiàn)。信息學(xué)奧林匹克IOI界的名人厉颤，獲得兩次金牌穴豫，一次銀牌。MIT博士逼友，師從神童教授Erik Demaine（沒(méi)讀中小學(xué)12歲上大學(xué)精肃，4年本科秤涩，1年master，1年phd司抱，20歲時(shí)博士畢業(yè)）
他在麻省的介紹：http://people.csail.mit.edu/mip/
維基百科的介紹：https://en.wikipedia.org/wiki/Mihai_P%C4%83tra%C8%99cu
所以這個(gè)僅用加減實(shí)現(xiàn)的二分查找的算法是Mihai P?tra?cu 提出的?(我也不確定)筐眷。那有了二分法搜索為什么又提出斐波那契搜索呢，是否斐波那契搜索比二分法搜索习柠，相信很多做完此題的讀者都會(huì)有這個(gè)疑問(wèn)浊竟，這里我在Stack Overflow幫大家找到了相應(yīng)的問(wèn)答，供大家參考：
Is fibonacci search faster than binary search?
大概的意思就是津畸，斐波那契查找的時(shí)間復(fù)雜度還是O(log2n )振定，但是與折半查找相比，對(duì)磁盤的操作更省力肉拓，因此后频，斐波那契查找的運(yùn)行時(shí)間理論上比折半查找小。最后我們對(duì)斐波那契搜索做個(gè)更加詳細(xì)的說(shuō)明：
斐波那契搜索就是在二分查找的基礎(chǔ)上根據(jù)斐波那契數(shù)列進(jìn)行分割的暖途。在斐波那契數(shù)列找一個(gè)等于略大于查找表中元素個(gè)數(shù)的數(shù)F[n]卑惜，將原查找表擴(kuò)展為長(zhǎng)度為Fn，完成后進(jìn)行斐波那契分割驻售，即F[n]個(gè)元素分割為前半部分F[n-1]個(gè)元素露久，后半部分F[n-2]個(gè)元素，找出要查找的元素在那一部分并遞歸欺栗，直到找到毫痕。
答案
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;
// 制造一個(gè)長(zhǎng)度為10的斐波數(shù)列
int[] fb = makeFbArray(FI_SIZE);
int k = 0;
// 找出數(shù)組的長(zhǎng)度在斐波數(shù)列（減1）中的位置，將決定如何拆分
while (length > fb[k] - 1) {
k++;
}
// 構(gòu)造一個(gè)長(zhǎng)度為fb[k] - 1的新數(shù)列
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) {
// 若相等則說(shuō)明mid即為查找到的位置
return middle;
} else {
// middle的值已經(jīng)大于hight,進(jìn)入擴(kuò)展數(shù)組的填充部分,
//即最后一個(gè)數(shù)就是要查找的數(shù)迟几。
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;
}
}
測(cè)試用例
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));
}
代碼索引
廣告
我的首款個(gè)人開(kāi)發(fā)的APP壁紙寶貝上線了消请，歡迎大家下載。
