前言

查詢演算法文章重置版

本文總結了常用的查詢演算法，內容包括：

查詢演算法的定義和思路，動畫演示

查詢演算法的程式碼實現：Python和Java

查詢演算法效能分析：時間空間複雜度分析

不同排序演算法最佳使用場景

面試知識點複習手冊

此文屬於知識點複習手冊專欄內容，你還可以

透過以下兩種途徑檢視全複習手冊文章導航

：

關注我的公眾號：Rude3Knife 點選公眾號下方：技術推文——面試衝刺

全複習手冊文章導航（CSDN）

-----正文開始-----

預備知識

查詢演算法分類

1）靜態查詢和動態查詢；

注：靜態或者動態都是針對查詢表而言的。動態表指查詢表中有刪除和插入操作的表。

2）無序查詢和有序查詢。

無序查詢：被查詢數列有序無序均可；

有序查詢：被查詢數列必須為有序數列。

平均查詢長度（Average Search Length，ASL）

需和指定key進行比較的關鍵字的個數的期望值

，稱為查詢演算法在查詢成功時的平均查詢長度。

對於含有n個數據元素的查詢表，查詢成功的平均查詢長度為：

ASL = Pi*Ci

的和。

Pi：查詢表中第i個數據元素的機率。

Ci：找到第i個數據元素時已經比較過的次數。

查詢效能

從快到慢：

順序查詢，時間複雜度O（N），

分塊查詢，

時間複雜度

O（logN+N/m）；

二分查詢，時間複雜度O（logN）

Fibonacci查詢，時間複雜度O（logN）

差值查詢，時間複雜度O（log（logN））

雜湊查詢，時間複雜度O（1）

查詢演算法

1. 順序查詢

說明：屬於有序查詢，順序查詢適合於儲存結構為順序儲存或連結儲存的

線性表

。

複雜度分析：

查詢成功時的平均查詢長度為：

（假設每個資料元素的機率相等）

ASL = 1/n（1+2+3+…+n） = （n+1）/2 ；

當查詢不成功時，需要n+1次比較，時間複雜度為

O(n)

；

所以，順序查詢的時間複雜度為

O(n)

。

Java實現：

public static int SequenceSearch（int a［］， int value， int n） {

for（int i=1；i

if（a［i］==value） {

return i；

}

}

return -1；

}

2.二分查詢

二分查詢經典理解：

https：//www。

zhihu。com/question/3613

2386/answer/155438728

基本思想：

也稱為是折半查詢，屬於有序查詢演算法。用給定值k先與中間結點的關鍵字比較，中間結點把線形表分成兩個子表，若相等則查詢成功；若不相等，再根據k與該中間結點關鍵字的比較結果確定下一步查詢哪個子表，這樣遞迴進行，直到查詢到或查詢結束髮現表中沒有這樣的結點。

複雜度分析：

最壞情況下，關鍵詞比較次數為log2（n+1），且期望時間複雜度為

O(log2n)

；對於一個有1024個元素的陣列，在最壞的情況下，二分查詢法只需要比較log2n + 1= 11次，而在最壞的情況下線性查詢要比較1023次。

注：折半查詢的前提條件是需要有序表順序儲存，對於靜態查詢表，一次排序後不再變化，折半查詢能得到不錯的效率。但對於需要頻繁執行插入或刪除操作的資料集來說，維護有序的排序會帶來不小的工作量，那就不建議使用。——《

大話資料結構

》

注意點：為什麼（low +high） / 2會溢位啊？答：兩個很大的int相加的話超出 Integer。MAX_VALUE 了

Java實現：

// 迭代版

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 應該插入的位置

}

// 遞迴版

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；

}

}

//含有重複數字的情況

//主要區別：等於mid也要將high-1；直到low>high結束，返回low（其實是高位，重複數字的第一位）

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 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.插值查詢

透過類比，我們可以將二分查詢的點改進為如下：

mid=low+（high-low）*（key-a［low］）/（a［high］-a［low］）//（1/2）換為（key-a［low］）/（a［high］-a［low］）

也就是將上述的比例引數1/2改進為自適應的，根據關鍵字在整個有序表中所處的位置，讓mid值的變化更靠近關鍵字key，這樣也就間接地減少了比較次數。

基本思想：

基於二分查詢演算法，將查詢點的選擇改進為自適應選擇，可以提高查詢效率。當然，差值查詢也屬於有序查詢。

注：對於表長較大，而關鍵字分佈又比較均勻的查詢表來說，插值查詢演算法的平均效能比折半查詢要好的多。反之，陣列中如果分佈非常不均勻，那麼插值查詢未必是很合適的選擇。

複雜度分析：

查詢成功或者失敗的時間複雜度均為

O(log2(log2n))

。

Java實現：

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

斐波那契查詢與折半查詢很相似，他是根據

斐波那契序列

的特點對有序表進行分割的。

他要求開始表中記錄的個數為某個斐波那契數小1

，n=F（k）-1；

複雜度分析：

最壞情況下，

時間複雜度為O(log2n)，且其期望複雜度也為O(log2n)

。

注意：生成的陣列長度是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；

// 斐波那契分割數值下標

int k = 0；

// 序列元素個數

int i = 0；

// 獲取

斐波那契數列

int［］ f = fibonacci（）；

// 獲取斐波那契分割數值下標

while （n > f［k］ - 1） {

k++；

}

// 建立臨時陣列

int［］ temp = new int［f［k］ - 1］；

for （int j = 0； j < n；j++） {

temp［j］ = a［j］；

}

// 序列補充至f［k］個元素

// 補充的元素值為最後一個元素的值

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］個元素，由於下標從0開始

// 則-1 獲取 黃金分割位置元素的下標

mid = low + f［k - 1］ - 1；

if （temp［mid］ > value） {

// 查詢前半部分，

高位指標

移動

high = mid - 1；

// （全部元素） = （前半部分）+（後半部分）

// f［k］ - 1 = f［k-1］ -1 + f［k-2］ -1

// 因為前半部分有f［k-1］個元素，所以 k = k-1

k = k - 1；

} else if （temp［mid］ < value） {

// 查詢後半部分，高位指標移動

low = mid + 1；

// （全部元素） = （前半部分）+（後半部分）

// f［k］ -1 = f［k-1］ -1 + f［k-2］ - 1

// 因為後半部分有f［k-2］個元素，所以 k = k-2

k = k - 2；

} else {

// 如果為真則找到相應的位置

if （mid <= high） {

return mid；

} else {

// 出現這種情況是查詢到補充的元素

// 而補充的元素與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.樹表查詢

5.1 最簡單的樹表查詢演算法——二叉樹查詢演算法

基本思想：

這個演算法的查詢效率很高，但是如果使用這種查詢方法要首先建立樹。

二叉查詢樹（BinarySearch Tree，也叫二叉搜尋樹，或稱

二叉排序樹Binar

y Sort Tree）或者是一棵空樹，或者是具有下列性質的二叉樹：

1）若任意節點的左子樹不空，則左子樹上所有結點的值均小於它的根結點的值；

2）若任意節點的右子樹不空，則右子樹上所有結點的值均大於它的根結點的值；

3）任意節點的左、右子樹也分別為二叉查詢樹。

二叉查詢樹性質：

對二叉查詢樹進行中序遍歷，即可得到有序的數列。

有關二叉查詢樹的查詢、插入、刪除等操作的詳細講解，請移步淺談演算法和資料結構： 七 二叉查詢樹

複雜度分析：

它和二分查詢一樣，插入和查詢的時間複雜度均為O（logn），但是在最壞的情況下仍然會有O（n）的時間複雜度。原因在於插入和刪除元素的時候，樹沒有保持平衡（比如，我們查詢上圖（b）中的“93”，我們需要進行n次查詢操作）。我們追求的是在最壞的情況下仍然有較好的時間複雜度，這就是平衡查詢樹設計的初衷。

基於二叉查詢樹進行最佳化，進而可以得到其他的樹表查詢演算法，如平衡樹、紅黑樹等高效演算法。

5.2 平衡查詢樹之2-3查詢樹（2-3 Tree）

https：//

riteme。github。io/blog/2

016-3-12/2-3-tree-and-red-black-tree。html

2-3查詢樹定義：和

二叉樹

不一樣，2-3樹執行每個節點儲存1個或者兩個的值。對於普通的2節點（2-node），他儲存1個key和左右兩個自己點。對應3節點（3-node），儲存兩個Key，2-3查詢樹的定義如下：

1）要麼為空，要麼：

2）對於2節點，該節點儲存一個key及對應value，以及兩個指向左右節點的節點，左節點也是一個2-3節點，所有的值都比key要小，右節點也是一個2-3節點，所有的值比key要大。

3）對於3節點，該節點儲存兩個key及對應value，以及三個指向左中右的節點。左節點也是一個2-3節點，所有的值均比兩個key中的最小的key還要小；

中間節點

也是一個2-3節點，中間節點的key值在兩個跟節點key值之間；右節點也是一個2-3節點，節點的所有key值比兩個key中的最大的key還要大。

2-3查詢樹的性質：

1）如果中序遍歷2-3查詢樹，就可以得到排好序的序列；

2）在一個完全平衡的2-3查詢樹中，根節點到每一個為空節點的距離都相同。（這也是平衡樹中“平衡”一詞的概念，根節點到葉節點的最長距離對應於查詢演算法的最壞情況，而平衡樹中根節點到葉節點的距離都一樣，最壞情況也具有對數複雜度。）

複雜度分析：

2-3樹的查詢效率與樹的高度是息息相關的。

距離來說，對於1百萬個節點的2-3樹，樹的高度為12-20之間，對於10億個節點的2-3樹，樹的高度為18-30之間。

對於插入來說，只需要常數次操作即可完成，因為他只需要修改與該節點關聯的節點即可，不需要檢查其他節點，所以效率和查詢類似。

5.3 平衡查詢樹之紅黑樹（Red-Black Tree）

但是2-3樹實現起來比較複雜，於是就有了一種簡單實現2-3樹的資料結構，即紅黑樹（Red-Black Tree）。

紅黑樹的定義：

紅黑樹是一種具有紅色和黑色連結的平衡查詢樹，同時滿足：

紅色節點向左傾斜

一個節點不可能有兩個紅色連結

整個樹完全黑色平衡，即從根節點到所以葉子結點的路徑上，黑色連結的個數都相同。

紅黑樹的性質：整個樹完全黑色平衡，即從根節點到所以葉子結點的路徑上，黑色連結的個數都相同（2-3樹的第2）性質，從根節點到葉子節點的距離都相等）。

複雜度分析：

最壞的情況就是，紅黑樹中除了最左側路徑全部是由3-node節點組成，即紅黑相間的

路徑長度

是全黑路徑長度的2倍。

下圖是一個典型的紅黑樹，從中可以看到最長的路徑（紅黑相間的路徑）是最短路徑的2倍：

紅黑樹這種資料結構應用十分廣泛，在多種程式語言中被用作符號表的實現，如：

Java中的java。util。TreeMap，java。util。TreeSet；

C++ STL中的：map，multimap，multiset；

。NET中的：SortedDictionary，SortedSet 等。

5.4 B樹和B+樹（B Tree/B+ Tree）

普遍運用在資料庫和檔案系統。

B樹可以看作是對2-3查詢樹的一種擴充套件，即他允許每個節點有M-1個子節點。

根節點至少有兩個子節點

每個節點有M-1個key，並且以升序排列

位於M-1和M key的子節點的值位於M-1 和M key對應的Value之間

其它節點至少有M/2個子節點

可以看到B樹是2-3樹的一種擴充套件，他允許一個節點有多於2個的元素。B樹的插入及平衡化操作和2-3樹很相似，這裡就不介紹了。

B+樹是對B樹的一種變形樹，它與B樹的差異在於：

有k個子結點的結點必然有k個關鍵碼；

非葉結點僅具有索引作用，跟記錄有關的資訊均存放在葉結點中。

樹的所有葉結點構成一個有序連結串列，可以按照關鍵碼排序的次序遍歷全部記錄。

B和B+樹的區別在於，B+樹的非葉子結點只包含導航資訊，不包含實際的值，所有的葉子結點和相連的節點使用連結串列相連，便於區間查詢和遍歷。

但是B樹也有優點，其優點在於，由於B樹的每一個節點都包含key和value，因此經常訪問的元素可能離根節點更近，因此訪問也更迅速。

Windows：HPFS檔案系統；

Mac：HFS，HFS+檔案系統；

Linux：ResiserFS，XFS，Ext3FS，JFS檔案系統；

資料庫：ORACLE，MYSQL，SQLSERVER等中。

樹表查詢總結：

二叉查詢樹平均查詢效能不錯，為O（logn），但是最壞情況會退化為O（n）。在二叉查詢樹的基礎上進行最佳化，我們可以使用平衡查詢樹。平衡查詢樹中的2-3查詢樹，這種資料結構在插入之後能夠進行自平衡操作，從而保證了樹的高度在一定的範圍內進而能夠保證最壞情況下的時間複雜度。但是2-3查詢樹實現起來比較困難，紅黑樹是2-3樹的一種簡單高效的實現，他巧妙地使用顏色標記來替代2-3樹中比較難處理的3-node節點問題。紅黑樹是一種比較高效的平衡查詢樹，應用非常廣泛，很多程式語言的內部實現都或多或少的採用了紅黑樹。

除此之外，2-3查詢樹的另一個擴充套件——B/B+平衡樹，在檔案系統和資料庫系統中有著廣泛的應用。

6. 分塊查詢

解釋：

https：//

blog。csdn。net/u01303627

4/article/details/49176027

屬於順序查詢，分塊查詢又稱

索引順序查詢

，它是順序查詢的一種改進方法。

演算法思想

：

將n個數據元素“按塊有序”劃分為m塊（m ≤ n）。每一塊中的結點不必有序，但塊與塊之間必須“按塊有序”；即第1塊中任一元素的關鍵字都必須小於第2塊中任一元素的關鍵字；而第2塊中任一元素又都必須小於第3塊中的任一元素，……

演算法流程：

step1 先選取各塊中的最大關鍵字構成一個索引表；

step2 查詢分兩個部分：先對索引表進行二分查詢或順序查詢，以確定待查記錄在哪一塊中；然後，在已確定的塊中用順序法進行查詢。

7.雜湊查詢

單純論查詢複雜度：對於無衝突的Hash表而言，查詢複雜度為O（1）（注意，在查詢之前我們需要構建相應的Hash表）。

常見的解決衝突的方法：

拉鍊法和線性探測法。

詳細的介紹可以參見：淺談演算法和資料結構： 十一 雜湊表。

附錄：

Java完整程式碼，帶有測試用例：

public class test {

public static int SequenceSearch（int a［］， int value， int n） {

for（int i=1；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；

// 斐波那契分割數值下標

int k = 0；

// 序列元素個數

int i = 0；

// 獲取斐波那契數列

int［］ f = fibonacci（）；

// 獲取斐波那契分割數值下標

while （n > f［k］ - 1） {

k++；

}

// 建立臨時陣列

int［］ temp = new int［f［k］ - 1］；

for （int j = 0； j < n；j++） {

temp［j］ = a［j］；

}

// 序列補充至f［k］個元素

// 補充的元素值為最後一個元素的值

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］個元素，由於下標從0開始

// 則-1 獲取 黃金分割位置元素的下標

mid = low + f［k - 1］ - 1；

if （temp［mid］ > value） {

// 查詢前半部分，高位指標移動

high = mid - 1；

// （全部元素） = （前半部分）+（後半部分）

// f［k］ - 1 = f［k-1］ -1 + f［k-2］ -1

// 因為前半部分有f［k-1］個元素，所以 k = k-1

k = k - 1；

} else if （temp［mid］ < value） {

// 查詢後半部分，高位指標移動

low = mid + 1；

// （全部元素） = （前半部分）+（後半部分）

// f［k］ -1 = f［k-1］ -1 + f［k-2］ - 1

// 因為後半部分有f［k-2］個元素，所以 k = k-2

k = k - 2；

} else {

// 如果為真則找到相應的位置

if （mid <= high） {

return mid；

} else {

// 出現這種情況是查詢到補充的元素

// 而補充的元素與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}；//帶重複元素

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）；

}

}

主要參考網頁

http：//www。

cnblogs。com/maybe2030/p

/4715035。html#_label6

-----正文結束-----

全複習手冊文章導航：透過以下兩種途徑檢視

關注我的公眾號：Rude3Knife 點選公眾號下方：技術推文——面試衝刺

全複習手冊文章導航（CSDN）

知識點複習手冊文章推薦

Java基礎知識點面試手冊

Java容器（List、Set、Map）知識點快速複習手冊

Java併發知識點快速複習手冊（上）

Java併發知識點快速複習手冊（下）

Java虛擬機器知識點快速複習手冊（上）

Java虛擬機器知識點快速複習手冊（下）

快速梳理23種常用的設計模式

Redis基礎知識點面試手冊

Leetcode題解分類彙總（前150題）

面試常問的小演算法總結

查詢演算法總結及其部分演算法實現Python/Java

排序演算法最強總結及其程式碼實現（Python/Java）

HTTP應知應會知識點複習手冊（上）

HTTP應知應會知識點複習手冊（下）

計算機網路基礎知識點快速複習手冊

海量資料處理問題知識點複習手冊

……等（

請檢視全複習手冊導航

）

關注我

我是蠻三刀把刀，目前為後臺開發工程師。主要關注後臺開發，網路安全，Python爬蟲等技術。

來微信和我聊聊：yangzd1102

Github：

https：//

github。com/qqxx6661

原創部落格主要內容

筆試面試複習知識點手冊

Leetcode演算法題解析（前150題）

劍指offer演算法題解析

Python爬蟲相關技術分析和實戰

後臺開發相關技術分析和實戰

同步更新以下部落格

1. Csdn

http：//

blog。csdn。net/qqxx6661

擁有專欄：

Leetcode題解（Java/Python）

Python爬蟲實戰

Java程式設計師知識點複習手冊

2. 知乎

https：//www。

zhihu。com/people/yang-z

hen-dong-1/

擁有專欄：

Java程式設計師面試複習手冊

LeetCode演算法題詳解與程式碼實現

後臺開發實戰

3. 掘金

https：//

juejin。im/user/5b48015c

e51d45191462ba55

4. 簡書

https：//www。

jianshu。com/u/b5f225ca2

376

個人公眾號：Rude3Knife

如果文章對你有幫助，不妨收藏起來並轉發給您的朋友們~