-----正文開(kāi)始-----
預(yù)備知識(shí)
查找算法分類
1）靜態(tài)查找和動(dòng)態(tài)查找；
注：靜態(tài)或者動(dòng)態(tài)都是針對(duì)查找表而言的。動(dòng)態(tài)表指查找表中有刪除和插入操作的表。
2）無(wú)序查找和有序查找。
- 無(wú)序查找：被查找數(shù)列有序無(wú)序均可；
- 有序查找：被查找數(shù)列必須為有序數(shù)列。
平均查找長(zhǎng)度（Average Search Length，ASL）
需和指定key進(jìn)行比較的關(guān)鍵字的個(gè)數(shù)的期望值，稱為查找算法在查找成功時(shí)的平均查找長(zhǎng)度。
對(duì)于含有n個(gè)數(shù)據(jù)元素的查找表，查找成功的平均查找長(zhǎng)度為：ASL = Pi*Ci的和。
Pi：查找表中第i個(gè)數(shù)據(jù)元素的概率。
Ci：找到第i個(gè)數(shù)據(jù)元素時(shí)已經(jīng)比較過(guò)的次數(shù)。
查找性能
從快到慢：
- 順序查找，時(shí)間復(fù)雜度O(N),
- 分塊查找，時(shí)間復(fù)雜度O(logN+N/m);
- 二分查找，時(shí)間復(fù)雜度O(logN)
- Fibonacci查找，時(shí)間復(fù)雜度O(logN)
- 差值查找，時(shí)間復(fù)雜度O(log(logN))
- 哈希查找，時(shí)間復(fù)雜度O(1)
查找算法
1. 順序查找
說(shuō)明：屬于有序查找，順序查找適合于存儲(chǔ)結(jié)構(gòu)為順序存儲(chǔ)或鏈接存儲(chǔ)的線性表。
復(fù)雜度分析：
查找成功時(shí)的平均查找長(zhǎng)度為：
（假設(shè)每個(gè)數(shù)據(jù)元素的概率相等） ASL = 1/n(1+2+3+…+n) = (n+1)/2 ;
當(dāng)查找不成功時(shí)，需要n+1次比較，時(shí)間復(fù)雜度為O(n);
所以，順序查找的時(shí)間復(fù)雜度為O(n)。
Java實(shí)現(xiàn)：
public static int SequenceSearch(int a[], int value, int n) {
for(int i=1;i<n;i++) {
if(a[i]==value) {
return i;
}
}
return -1;
}
2.二分查找
基本思想：
也稱為是折半查找，屬于有序查找算法。用給定值k先與中間結(jié)點(diǎn)的關(guān)鍵字比較，中間結(jié)點(diǎn)把線形表分成兩個(gè)子表，若相等則查找成功；若不相等，再根據(jù)k與該中間結(jié)點(diǎn)關(guān)鍵字的比較結(jié)果確定下一步查找哪個(gè)子表，這樣遞歸進(jìn)行，直到查找到或查找結(jié)束發(fā)現(xiàn)表中沒(méi)有這樣的結(jié)點(diǎn)。
復(fù)雜度分析：
最壞情況下，關(guān)鍵詞比較次數(shù)為log2(n+1)，且期望時(shí)間復(fù)雜度為O(log2n)；對(duì)于一個(gè)有1024個(gè)元素的數(shù)組，在最壞的情況下，二分查找法只需要比較log2n + 1= 11次，而在最壞的情況下線性查找要比較1023次。
注：折半查找的前提條件是需要有序表順序存儲(chǔ)，對(duì)于靜態(tài)查找表，一次排序后不再變化，折半查找能得到不錯(cuò)的效率。但對(duì)于需要頻繁執(zhí)行插入或刪除操作的數(shù)據(jù)集來(lái)說(shuō)，維護(hù)有序的排序會(huì)帶來(lái)不小的工作量，那就不建議使用。——《大話數(shù)據(jù)結(jié)構(gòu)》
注意點(diǎn)：為什么(low +high) / 2會(huì)溢出?。看穑簝蓚€(gè)很大的int相加的話超出 Integer.MAX_VALUE 了
Java實(shí)現(xiàn)：
// 迭代版
public static int BinarySearch(int a[], int value, int n) {
int low = 0;
int high = n-1;
int mid = 0;
while (low <= high) {
mid = low + (high - low) * 1/2;
if(a[mid] == value) {
return mid;
}
if(a[mid] > value) {
high = mid - 1;
}
else {
low = mid + 1;
}
}
return -1; //return low 應(yīng)該插入的位置
}
// 遞歸版
public int binarySearchRecur(int[] nums, int target, int low, int high) {
if (low > high) { return low; } //base case
int mid = low + (high - low) / 2;
if (nums[mid] > target) {
return binarySearchRecur(nums,target,low,mid-1);
} else if (nums[mid] < target) {
return binarySearchRecur(nums,target,mid+1,high);
} else {
return mid;
}
}
//含有重復(fù)數(shù)字的情況
//主要區(qū)別：等于mid也要將high-1；直到low>high結(jié)束，返回low（其實(shí)是高位，重復(fù)數(shù)字的第一位）
public static int BinarySearchDuplicate(int a[], int value, int n) {
int low = 0;
int high = n-1;
int mid = 0;
while (low <= high) {
mid = low + (high - low) * 1/2;
if(a[mid] >= value) {
high = mid - 1;
}
else {
low = mid + 1;
}
}
return low;
}
//含有重復(fù)數(shù)字：遞歸版
public int firstOccurrenceRecur(int[] nums, int target, int low, int high) {
if (low > high) { return low; }
int mid = low + (high - low) / 2;
if (nums[mid] < target) {
return firstOccurrenceRecur(nums,target,mid + 1,high);
} else {
return firstOccurrenceRecur(nums,target,low,mid-1);
}
}
3.插值查找
通過(guò)類比，我們可以將二分查找的點(diǎn)改進(jìn)為如下：
mid=low+(high-low)*(key-a[low])/(a[high]-a[low])//(1/2)換為(key-a[low])/(a[high]-a[low])
也就是將上述的比例參數(shù)1/2改進(jìn)為自適應(yīng)的，根據(jù)關(guān)鍵字在整個(gè)有序表中所處的位置，讓mid值的變化更靠近關(guān)鍵字key，這樣也就間接地減少了比較次數(shù)。
基本思想：
基于二分查找算法，將查找點(diǎn)的選擇改進(jìn)為自適應(yīng)選擇，可以提高查找效率。當(dāng)然，差值查找也屬于有序查找。
注：對(duì)于表長(zhǎng)較大，而關(guān)鍵字分布又比較均勻的查找表來(lái)說(shuō)，插值查找算法的平均性能比折半查找要好的多。反之，數(shù)組中如果分布非常不均勻，那么插值查找未必是很合適的選擇。
復(fù)雜度分析：
查找成功或者失敗的時(shí)間復(fù)雜度均為O(log2(log2n))。
Java實(shí)現(xiàn)：
public static int InsertionSearch(int a[], int value, int n) {
int low = 0;
int high = n-1;
int mid = 0;
while (low <= high) {
mid = low + (high-low) * (value-a[low]) / (a[high]-a[low]);
if(a[mid] == value) {
return mid;
}
if(a[mid] > value) {
high = mid - 1;
}
else {
low = mid + 1;
}
}
return -1;
}
4. 斐波那契查找
https://blog.csdn.net/zsw12013/article/details/50003505
[圖片上傳失敗...(image-97e793-1551795346605)]
斐波那契查找與折半查找很相似，他是根據(jù)斐波那契序列的特點(diǎn)對(duì)有序表進(jìn)行分割的。他要求開(kāi)始表中記錄的個(gè)數(shù)為某個(gè)斐波那契數(shù)小1，n=F(k)-1;
復(fù)雜度分析：
最壞情況下，時(shí)間復(fù)雜度為O(log2n)，且其期望復(fù)雜度也為O(log2n)。
注意：生成的數(shù)組長(zhǎng)度是f[k]-1而不是f[k]
Java：
public final static int MAXSIZE = 20; // fib length
public static int[] fibonacci() {
int[] f = new int[MAXSIZE];
int i = 0;
f[0] = 1;
f[1] = 1;
for (i = 2; i < MAXSIZE; i++) {
f[i] = f[i - 1] + f[i - 2];
}
return f;
}
public static int fibonacciSearch(int[] a, int value, int n) {
int low = 0;
int high = n - 1;
int mid = 0;
// 斐波那契分割數(shù)值下標(biāo)
int k = 0;
// 序列元素個(gè)數(shù)
int i = 0;
// 獲取斐波那契數(shù)列
int[] f = fibonacci();
// 獲取斐波那契分割數(shù)值下標(biāo)
while (n > f[k] - 1) {
k++;
}
// 創(chuàng)建臨時(shí)數(shù)組
int[] temp = new int[f[k] - 1];
for (int j = 0; j < n;j++) {
temp[j] = a[j];
}
// 序列補(bǔ)充至f[k]個(gè)元素
// 補(bǔ)充的元素值為最后一個(gè)元素的值
for (i = n; i < f[k] - 1; i++) {
temp[i] = temp[high];
}
// for (int j : temp) {
// System.out.print(j + " ");
// }
// System.out.println();
while (low <= high) {
// low：起始位置
// 前半部分有f[k-1]個(gè)元素，由于下標(biāo)從0開(kāi)始
// 則-1 獲取 黃金分割位置元素的下標(biāo)
mid = low + f[k - 1] - 1;
if (temp[mid] > value) {
// 查找前半部分，高位指針移動(dòng)
high = mid - 1;
// （全部元素） = （前半部分）+（后半部分）
// f[k] - 1 = f[k-1] -1 + f[k-2] -1
// 因?yàn)榍鞍氩糠钟衒[k-1]個(gè)元素，所以 k = k-1
k = k - 1;
} else if (temp[mid] < value) {
// 查找后半部分，高位指針移動(dòng)
low = mid + 1;
// （全部元素） = （前半部分）+（后半部分）
// f[k] -1 = f[k-1] -1 + f[k-2] - 1
// 因?yàn)楹蟀氩糠钟衒[k-2]個(gè)元素，所以 k = k-2
k = k - 2;
} else {
// 如果為真則找到相應(yīng)的位置
if (mid <= high) {
return mid;
} else {
// 出現(xiàn)這種情況是查找到補(bǔ)充的元素
// 而補(bǔ)充的元素與high位置的元素一樣
return high;
}
}
}
return -1;
}
Python：
MAXSIZE = 20
def fibonacci(): # 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89
f = [0] * MAXSIZE
f[0] = 1
f[1] = 1
for i in range(2, MAXSIZE):
f[i] = f[i-1] + f[i-2]
return f
def fibonacciSearch(array, value):
low, mid, high = 0, 0, len(array)-1
k = 0
f = fibonacci()
while len(array) > f[k]-1:
k += 1
temp = array + [array[-1] * (f[k]-1-len(array))]
while low <= high:
mid = low + f[k-1] - 1
if temp[mid] > value:
high = mid - 1
k = k - 1
elif temp[mid] < value:
low = mid + 1
k = k - 2
else:
if mid <= high: # 如果在high位前，則返回mid位置，否則返回high位置
return mid
else:
return high
return -1
if __name__ == '__main__':
a = [1, 3, 5, 6, 7, 88]
print(fibonacciSearch(a, 2))
5.樹(shù)表查找
5.1 最簡(jiǎn)單的樹(shù)表查找算法——二叉樹(shù)查找算法
基本思想：
這個(gè)算法的查找效率很高，但是如果使用這種查找方法要首先創(chuàng)建樹(shù)。
二叉查找樹(shù)（BinarySearch Tree，也叫二叉搜索樹(shù)，或稱二叉排序樹(shù)Binary Sort Tree）或者是一棵空樹(shù)，或者是具有下列性質(zhì)的二叉樹(shù)：
1）若任意節(jié)點(diǎn)的左子樹(shù)不空，則左子樹(shù)上所有結(jié)點(diǎn)的值均小于它的根結(jié)點(diǎn)的值；
2）若任意節(jié)點(diǎn)的右子樹(shù)不空，則右子樹(shù)上所有結(jié)點(diǎn)的值均大于它的根結(jié)點(diǎn)的值；
3）任意節(jié)點(diǎn)的左、右子樹(shù)也分別為二叉查找樹(shù)。
二叉查找樹(shù)性質(zhì)：
對(duì)二叉查找樹(shù)進(jìn)行中序遍歷，即可得到有序的數(shù)列。
復(fù)雜度分析：
它和二分查找一樣，插入和查找的時(shí)間復(fù)雜度均為O(logn)，但是在最壞的情況下仍然會(huì)有O(n)的時(shí)間復(fù)雜度。原因在于插入和刪除元素的時(shí)候，樹(shù)沒(méi)有保持平衡（比如，我們查找上圖（b）中的“93”，我們需要進(jìn)行n次查找操作）。我們追求的是在最壞的情況下仍然有較好的時(shí)間復(fù)雜度，這就是平衡查找樹(shù)設(shè)計(jì)的初衷。
基于二叉查找樹(shù)進(jìn)行優(yōu)化，進(jìn)而可以得到其他的樹(shù)表查找算法，如平衡樹(shù)、紅黑樹(shù)等高效算法。
5.2 平衡查找樹(shù)之2-3查找樹(shù)（2-3 Tree）
2-3查找樹(shù)定義：和二叉樹(shù)不一樣，2-3樹(shù)運(yùn)行每個(gè)節(jié)點(diǎn)保存1個(gè)或者兩個(gè)的值。對(duì)于普通的2節(jié)點(diǎn)(2-node)，他保存1個(gè)key和左右兩個(gè)自己點(diǎn)。對(duì)應(yīng)3節(jié)點(diǎn)(3-node)，保存兩個(gè)Key，2-3查找樹(shù)的定義如下：
1）要么為空，要么：
2）對(duì)于2節(jié)點(diǎn)，該節(jié)點(diǎn)保存一個(gè)key及對(duì)應(yīng)value，以及兩個(gè)指向左右節(jié)點(diǎn)的節(jié)點(diǎn)，左節(jié)點(diǎn)也是一個(gè)2-3節(jié)點(diǎn)，所有的值都比key要小，右節(jié)點(diǎn)也是一個(gè)2-3節(jié)點(diǎn)，所有的值比key要大。
3）對(duì)于3節(jié)點(diǎn)，該節(jié)點(diǎn)保存兩個(gè)key及對(duì)應(yīng)value，以及三個(gè)指向左中右的節(jié)點(diǎn)。左節(jié)點(diǎn)也是一個(gè)2-3節(jié)點(diǎn)，所有的值均比兩個(gè)key中的最小的key還要小；中間節(jié)點(diǎn)也是一個(gè)2-3節(jié)點(diǎn)，中間節(jié)點(diǎn)的key值在兩個(gè)跟節(jié)點(diǎn)key值之間；右節(jié)點(diǎn)也是一個(gè)2-3節(jié)點(diǎn)，節(jié)點(diǎn)的所有key值比兩個(gè)key中的最大的key還要大。
2-3查找樹(shù)的性質(zhì)：
1）如果中序遍歷2-3查找樹(shù)，就可以得到排好序的序列；
2）在一個(gè)完全平衡的2-3查找樹(shù)中，根節(jié)點(diǎn)到每一個(gè)為空節(jié)點(diǎn)的距離都相同。（這也是平衡樹(shù)中“平衡”一詞的概念，根節(jié)點(diǎn)到葉節(jié)點(diǎn)的最長(zhǎng)距離對(duì)應(yīng)于查找算法的最壞情況，而平衡樹(shù)中根節(jié)點(diǎn)到葉節(jié)點(diǎn)的距離都一樣，最壞情況也具有對(duì)數(shù)復(fù)雜度。）
復(fù)雜度分析：
2-3樹(shù)的查找效率與樹(shù)的高度是息息相關(guān)的。
距離來(lái)說(shuō)，對(duì)于1百萬(wàn)個(gè)節(jié)點(diǎn)的2-3樹(shù)，樹(shù)的高度為12-20之間，對(duì)于10億個(gè)節(jié)點(diǎn)的2-3樹(shù)，樹(shù)的高度為18-30之間。
對(duì)于插入來(lái)說(shuō)，只需要常數(shù)次操作即可完成，因?yàn)樗恍枰薷呐c該節(jié)點(diǎn)關(guān)聯(lián)的節(jié)點(diǎn)即可，不需要檢查其他節(jié)點(diǎn)，所以效率和查找類似。
5.3 平衡查找樹(shù)之紅黑樹(shù)（Red-Black Tree）
但是2-3樹(shù)實(shí)現(xiàn)起來(lái)比較復(fù)雜，于是就有了一種簡(jiǎn)單實(shí)現(xiàn)2-3樹(shù)的數(shù)據(jù)結(jié)構(gòu)，即紅黑樹(shù)（Red-Black Tree）。
紅黑樹(shù)的定義：
紅黑樹(shù)是一種具有紅色和黑色鏈接的平衡查找樹(shù)，同時(shí)滿足：
紅色節(jié)點(diǎn)向左傾斜
一個(gè)節(jié)點(diǎn)不可能有兩個(gè)紅色鏈接
整個(gè)樹(shù)完全黑色平衡，即從根節(jié)點(diǎn)到所以葉子結(jié)點(diǎn)的路徑上，黑色鏈接的個(gè)數(shù)都相同。
紅黑樹(shù)的性質(zhì)：整個(gè)樹(shù)完全黑色平衡，即從根節(jié)點(diǎn)到所以葉子結(jié)點(diǎn)的路徑上，黑色鏈接的個(gè)數(shù)都相同（2-3樹(shù)的第2）性質(zhì)，從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)的距離都相等）。
復(fù)雜度分析：
最壞的情況就是，紅黑樹(shù)中除了最左側(cè)路徑全部是由3-node節(jié)點(diǎn)組成，即紅黑相間的路徑長(zhǎng)度是全黑路徑長(zhǎng)度的2倍。
下圖是一個(gè)典型的紅黑樹(shù)，從中可以看到最長(zhǎng)的路徑(紅黑相間的路徑)是最短路徑的2倍：
紅黑樹(shù)這種數(shù)據(jù)結(jié)構(gòu)應(yīng)用十分廣泛，在多種編程語(yǔ)言中被用作符號(hào)表的實(shí)現(xiàn)，如：
Java中的java.util.TreeMap,java.util.TreeSet；
C++ STL中的：map,multimap,multiset；
.NET中的：SortedDictionary,SortedSet 等。
5.4 B樹(shù)和B+樹(shù)（B Tree/B+ Tree）
普遍運(yùn)用在數(shù)據(jù)庫(kù)和文件系統(tǒng)。
B樹(shù)可以看作是對(duì)2-3查找樹(shù)的一種擴(kuò)展，即他允許每個(gè)節(jié)點(diǎn)有M-1個(gè)子節(jié)點(diǎn)。
根節(jié)點(diǎn)至少有兩個(gè)子節(jié)點(diǎn)
每個(gè)節(jié)點(diǎn)有M-1個(gè)key，并且以升序排列
位于M-1和M key的子節(jié)點(diǎn)的值位于M-1 和M key對(duì)應(yīng)的Value之間
其它節(jié)點(diǎn)至少有M/2個(gè)子節(jié)點(diǎn)
可以看到B樹(shù)是2-3樹(shù)的一種擴(kuò)展，他允許一個(gè)節(jié)點(diǎn)有多于2個(gè)的元素。B樹(shù)的插入及平衡化操作和2-3樹(shù)很相似，這里就不介紹了。
下面是往B樹(shù)中依次插入6 10 4 14 5 11 15 3 2 12 1 7 8 8 6 3 6 21 5 15 15 6 32 23 45 65 7 8 6 5 4
B+樹(shù)是對(duì)B樹(shù)的一種變形樹(shù)，它與B樹(shù)的差異在于：
有k個(gè)子結(jié)點(diǎn)的結(jié)點(diǎn)必然有k個(gè)關(guān)鍵碼；
非葉結(jié)點(diǎn)僅具有索引作用，跟記錄有關(guān)的信息均存放在葉結(jié)點(diǎn)中。
樹(shù)的所有葉結(jié)點(diǎn)構(gòu)成一個(gè)有序鏈表，可以按照關(guān)鍵碼排序的次序遍歷全部記錄。
B和B+樹(shù)的區(qū)別在于，B+樹(shù)的非葉子結(jié)點(diǎn)只包含導(dǎo)航信息，不包含實(shí)際的值，所有的葉子結(jié)點(diǎn)和相連的節(jié)點(diǎn)使用鏈表相連，便于區(qū)間查找和遍歷。
但是B樹(shù)也有優(yōu)點(diǎn)，其優(yōu)點(diǎn)在于，由于B樹(shù)的每一個(gè)節(jié)點(diǎn)都包含key和value，因此經(jīng)常訪問(wèn)的元素可能離根節(jié)點(diǎn)更近，因此訪問(wèn)也更迅速。
Windows：HPFS文件系統(tǒng)；
Mac：HFS，HFS+文件系統(tǒng)；
Linux：ResiserFS，XFS，Ext3FS，JFS文件系統(tǒng)；
數(shù)據(jù)庫(kù)：ORACLE，MYSQL，SQLSERVER等中。
樹(shù)表查找總結(jié)：
二叉查找樹(shù)平均查找性能不錯(cuò)，為O(logn)，但是最壞情況會(huì)退化為O(n)。在二叉查找樹(shù)的基礎(chǔ)上進(jìn)行優(yōu)化，我們可以使用平衡查找樹(shù)。平衡查找樹(shù)中的2-3查找樹(shù)，這種數(shù)據(jù)結(jié)構(gòu)在插入之后能夠進(jìn)行自平衡操作，從而保證了樹(shù)的高度在一定的范圍內(nèi)進(jìn)而能夠保證最壞情況下的時(shí)間復(fù)雜度。但是2-3查找樹(shù)實(shí)現(xiàn)起來(lái)比較困難，紅黑樹(shù)是2-3樹(shù)的一種簡(jiǎn)單高效的實(shí)現(xiàn)，他巧妙地使用顏色標(biāo)記來(lái)替代2-3樹(shù)中比較難處理的3-node節(jié)點(diǎn)問(wèn)題。紅黑樹(shù)是一種比較高效的平衡查找樹(shù)，應(yīng)用非常廣泛，很多編程語(yǔ)言的內(nèi)部實(shí)現(xiàn)都或多或少的采用了紅黑樹(shù)。
除此之外，2-3查找樹(shù)的另一個(gè)擴(kuò)展——B/B+平衡樹(shù)，在文件系統(tǒng)和數(shù)據(jù)庫(kù)系統(tǒng)中有著廣泛的應(yīng)用。
6. 分塊查找
屬于順序查找，分塊查找又稱索引順序查找，它是順序查找的一種改進(jìn)方法。
算法思想：
將n個(gè)數(shù)據(jù)元素"按塊有序"劃分為m塊（m ≤ n）。每一塊中的結(jié)點(diǎn)不必有序，但塊與塊之間必須"按塊有序"；即第1塊中任一元素的關(guān)鍵字都必須小于第2塊中任一元素的關(guān)鍵字；而第2塊中任一元素又都必須小于第3塊中的任一元素，……
算法流程：
step1 先選取各塊中的最大關(guān)鍵字構(gòu)成一個(gè)索引表；
step2 查找分兩個(gè)部分：先對(duì)索引表進(jìn)行二分查找或順序查找，以確定待查記錄在哪一塊中；然后，在已確定的塊中用順序法進(jìn)行查找。
7.哈希查找
單純論查找復(fù)雜度：對(duì)于無(wú)沖突的Hash表而言，查找復(fù)雜度為O(1)（注意，在查找之前我們需要構(gòu)建相應(yīng)的Hash表）。
常見(jiàn)的解決沖突的方法：拉鏈法和線性探測(cè)法。
附錄：
Java完整代碼，帶有測(cè)試用例：
public class test {
public static int SequenceSearch(int a[], int value, int n) {
for(int i=1;i<n;i++) {
if(a[i]==value) {
return i;
}
}
return -1;
}
public static int BinarySearch(int a[], int value, int n) {
int low = 0;
int high = n-1;
int mid = 0;
while (low <= high) {
mid = low + (high - low) * 1/2;
if(a[mid] == value) {
return mid;
}
if(a[mid] > value) {
high = mid - 1;
}
else {
low = mid + 1;
}
}
return -1;
}
public static int BinarySearchDuplicate(int a[], int value, int n) {
int low = 0;
int high = n-1;
int mid = 0;
while (low <= high) {
mid = low + (high - low) * 1/2;
if(a[mid] >= value) {
high = mid - 1;
}
else {
low = mid + 1;
}
}
return low;
}
public static int InsertionSearch(int a[], int value, int n) {
int low = 0;
int high = n-1;
int mid = 0;
while (low <= high) {
mid = low + (high-low) * (value-a[low]) / (a[high]-a[low]);
if(a[mid] == value) {
return mid;
}
if(a[mid] > value) {
high = mid - 1;
}
else {
low = mid + 1;
}
}
return -1;
}
public final static int MAXSIZE = 20; // fib length
public static int[] fibonacci() {
int[] f = new int[MAXSIZE];
int i = 0;
f[0] = 1;
f[1] = 1;
for (i = 2; i < MAXSIZE; i++) {
f[i] = f[i - 1] + f[i - 2];
}
return f;
}
public static int fibonacciSearch(int[] a, int value, int n) {
int low = 0;
int high = n - 1;
int mid = 0;
// 斐波那契分割數(shù)值下標(biāo)
int k = 0;
// 序列元素個(gè)數(shù)
int i = 0;
// 獲取斐波那契數(shù)列
int[] f = fibonacci();
// 獲取斐波那契分割數(shù)值下標(biāo)
while (n > f[k] - 1) {
k++;
}
// 創(chuàng)建臨時(shí)數(shù)組
int[] temp = new int[f[k] - 1];
for (int j = 0; j < n;j++) {
temp[j] = a[j];
}
// 序列補(bǔ)充至f[k]個(gè)元素
// 補(bǔ)充的元素值為最后一個(gè)元素的值
for (i = n; i < f[k] - 1; i++) {
temp[i] = temp[high];
}
// for (int j : temp) {
// System.out.print(j + " ");
// }
// System.out.println();
while (low <= high) {
// low：起始位置
// 前半部分有f[k-1]個(gè)元素，由于下標(biāo)從0開(kāi)始
// 則-1 獲取 黃金分割位置元素的下標(biāo)
mid = low + f[k - 1] - 1;
if (temp[mid] > value) {
// 查找前半部分，高位指針移動(dòng)
high = mid - 1;
// （全部元素） = （前半部分）+（后半部分）
// f[k] - 1 = f[k-1] -1 + f[k-2] -1
// 因?yàn)榍鞍氩糠钟衒[k-1]個(gè)元素，所以 k = k-1
k = k - 1;
} else if (temp[mid] < value) {
// 查找后半部分，高位指針移動(dòng)
low = mid + 1;
// （全部元素） = （前半部分）+（后半部分）
// f[k] -1 = f[k-1] -1 + f[k-2] - 1
// 因?yàn)楹蟀氩糠钟衒[k-2]個(gè)元素，所以 k = k-2
k = k - 2;
} else {
// 如果為真則找到相應(yīng)的位置
if (mid <= high) {
return mid;
} else {
// 出現(xiàn)這種情況是查找到補(bǔ)充的元素
// 而補(bǔ)充的元素與high位置的元素一樣
return high;
}
}
}
return -1;
}
public static void main(String[] args) {
int[] a = {1,5,2,7,3,9};
int[] b = {1,3,5,6,7,88};
int[] c = {1,3,5,7,7,88};//帶重復(fù)元素
int value = 5;
int n1 = a.length;
int n2 = b.length;
int n3 = c.length;
// int result = SequenceSearch(a, value, n1);
// int result = BinarySearch(b, value, n2);
// int result = BinarySearchDuplicate(c, value, n3);
// int result = InsertionSearch(b, value, n2);
int result = fibonacciSearch(b, value, n2);
System.out.println(result);
}
}
