查找算法最強總結及其算法實現

在這里插入圖片描述

前言

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

查找算法的定義和思路，動畫演示
查找算法的代碼實現：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實現：

2.二分查找

二分查找經典理解：https://www.zhihu.com/question/36132386/answer/155438728

基本思想：

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

復雜度分析：

最壞情況下，關鍵詞比較次數為log2(n+1)，且期望時間復雜度為O(log2n)；對于一個有1024個元素的數組，在最壞的情況下，二分查找法只需要比較log2n + 1= 11次，而在最壞的情況下線性查找要比較1023次。

注：折半查找的前提條件是需要有序表順序存儲，對于靜態查找表，一次排序后不再變化，折半查找能得到不錯的效率。但對于需要頻繁執行插入或刪除操作的數據集來說，維護有序的排序會帶來不小的工作量，那就不建議使用。——《大話數據結構》
注意點：為什么(low +high) / 2會溢出?。看穑簝蓚€很大的int相加的話超出 Integer.MAX_VALUE 了

Java實現：

3.插值查找

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

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

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

注：對于表長較大，而關鍵字分布又比較均勻的查找表來說，插值查找算法的平均性能比折半查找要好的多。反之，數組中如果分布非常不均勻，那么插值查找未必是很合適的選擇。

復雜度分析：

查找成功或者失敗的時間復雜度均為O(log2(log2n))。

Java實現：

4. 斐波那契查找

https://blog.csdn.net/zsw12013/article/details/50003505

[圖片上傳失敗…(image-97e793-1551795346605)]

斐波那契查找與折半查找很相似，他是根據斐波那契序列的特點對有序表進行分割的。他要求開始表中記錄的個數為某個斐波那契數小1，n=F(k)-1;

復雜度分析：
最壞情況下，時間復雜度為O(log2n)，且其期望復雜度也為O(log2n)。

注意：生成的數組長度是f[k]-1而不是f[k]

Java：

Python：

5.樹表查找

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

基本思想：

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

二叉查找樹（BinarySearch Tree，也叫二叉搜索樹，或稱二叉排序樹Binary Sort Tree）或者是一棵空樹，或者是具有下列性質的二叉樹：

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

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

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

二叉查找樹性質：

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

有關二叉查找樹的查找、插入、刪除等操作的詳細講解，請移步淺談算法和數據結構: 七二叉查找樹

復雜度分析：

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

基于二叉查找樹進行優化，進而可以得到其他的樹表查找算法，如平衡樹、紅黑樹等高效算法。

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

https://riteme.github.io/blog/2016-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還要?。恢虚g節點也是一個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樹中依次插入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+樹是對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/u013036274/article/details/49176027

屬于順序查找，分塊查找又稱索引順序查找，它是順序查找的一種改進方法。

[圖片上傳失敗…(image-fd2e41-1551795346605)]

算法思想：

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

算法流程：

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

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

7.哈希查找

單純論查找復雜度：對于無沖突的Hash表而言，查找復雜度為O(1)（注意，在查找之前我們需要構建相應的Hash表）。