查找算法最強(qiáng)總結(jié)及其算法實(shí)現(xiàn)

在這里插入圖片描述

前言

本文總結(jié)了常用的查找算法，內(nèi)容包括：

查找算法的定義和思路，動(dòng)畫演示
查找算法的代碼實(shí)現(xiàn)：Python和JAVA
查找算法性能分析：時(shí)間空間復(fù)雜度分析
不同排序算法最佳使用場(chǎng)景

面試知識(shí)點(diǎn)復(fù)習(xí)手冊(cè)

此文屬于知識(shí)點(diǎn)復(fù)習(xí)手冊(cè)專欄內(nèi)容，你還可以通過(guò)以下兩種途徑查看全復(fù)習(xí)手冊(cè)文章導(dǎo)航：

關(guān)注我的公眾號(hào)：Rude3Knife 點(diǎn)擊公眾號(hào)下方：技術(shù)推文——面試沖刺
全復(fù)習(xí)手冊(cè)文章導(dǎo)航(CSDN)

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

預(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)：

2.二分查找

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

基本思想：

也稱為是折半查找，屬于有序查找算法。用給定值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)表中沒有這樣的結(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)：

3.插值查找

通過(guò)類比，我們可以將二分查找的點(diǎn)改進(jìn)為如下：

也就是將上述的比例參數(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)：

4. 斐波那契查找

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

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

斐波那契查找與折半查找很相似，他是根據(jù)斐波那契序列的特點(diǎn)對(duì)有序表進(jìn)行分割的。他要求開始表中記錄的個(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：

Python：

5.樹表查找

5.1 最簡(jiǎn)單的樹表查找算法——二叉樹查找算法

基本思想：

這個(gè)算法的查找效率很高，但是如果使用這種查找方法要首先創(chuàng)建樹。

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

1）若任意節(jié)點(diǎn)的左子樹不空，則左子樹上所有結(jié)點(diǎn)的值均小于它的根結(jié)點(diǎn)的值；

2）若任意節(jié)點(diǎn)的右子樹不空，則右子樹上所有結(jié)點(diǎn)的值均大于它的根結(jié)點(diǎn)的值；

3）任意節(jié)點(diǎn)的左、右子樹也分別為二叉查找樹。

二叉查找樹性質(zhì)：

對(duì)二叉查找樹進(jìn)行中序遍歷，即可得到有序的數(shù)列。

有關(guān)二叉查找樹的查找、插入、刪除等操作的詳細(xì)講解，請(qǐng)移步淺談算法和數(shù)據(jù)結(jié)構(gòu): 七二叉查找樹

復(fù)雜度分析：

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

基于二叉查找樹進(jìn)行優(yōu)化，進(jì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樹運(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查找樹的定義如下：

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查找樹的性質(zhì)：

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

2）在一個(gè)完全平衡的2-3查找樹中，根節(jié)點(diǎn)到每一個(gè)為空節(jié)點(diǎn)的距離都相同。（這也是平衡樹中“平衡”一詞的概念，根節(jié)點(diǎn)到葉節(jié)點(diǎn)的最長(zhǎng)距離對(duì)應(yīng)于查找算法的最壞情況，而平衡樹中根節(jié)點(diǎn)到葉節(jié)點(diǎn)的距離都一樣，最壞情況也具有對(duì)數(shù)復(fù)雜度。）
復(fù)雜度分析：

2-3樹的查找效率與樹的高度是息息相關(guān)的。

距離來(lái)說(shuō)，對(duì)于1百萬(wàn)個(gè)節(jié)點(diǎn)的2-3樹，樹的高度為12-20之間，對(duì)于10億個(gè)節(jié)點(diǎn)的2-3樹，樹的高度為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 平衡查找樹之紅黑樹（Red-Black Tree）

但是2-3樹實(shí)現(xiàn)起來(lái)比較復(fù)雜，于是就有了一種簡(jiǎn)單實(shí)現(xiàn)2-3樹的數(shù)據(jù)結(jié)構(gòu)，即紅黑樹（Red-Black Tree）。

紅黑樹的定義：

紅黑樹是一種具有紅色和黑色鏈接的平衡查找樹，同時(shí)滿足：

紅色節(jié)點(diǎn)向左傾斜
一個(gè)節(jié)點(diǎn)不可能有兩個(gè)紅色鏈接
整個(gè)樹完全黑色平衡，即從根節(jié)點(diǎn)到所以葉子結(jié)點(diǎn)的路徑上，黑色鏈接的個(gè)數(shù)都相同。

紅黑樹的性質(zhì)：整個(gè)樹完全黑色平衡，即從根節(jié)點(diǎn)到所以葉子結(jié)點(diǎn)的路徑上，黑色鏈接的個(gè)數(shù)都相同（2-3樹的第2）性質(zhì)，從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)的距離都相等）。

這里寫圖片描述

復(fù)雜度分析：

最壞的情況就是，紅黑樹中除了最左側(cè)路徑全部是由3-node節(jié)點(diǎn)組成，即紅黑相間的路徑長(zhǎng)度是全黑路徑長(zhǎng)度的2倍。

下圖是一個(gè)典型的紅黑樹，從中可以看到最長(zhǎng)的路徑(紅黑相間的路徑)是最短路徑的2倍：

這里寫圖片描述

紅黑樹這種數(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樹和B+樹（B Tree/B+ Tree）

普遍運(yùn)用在數(shù)據(jù)庫(kù)和文件系統(tǒng)。

B樹可以看作是對(duì)2-3查找樹的一種擴(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樹是2-3樹的一種擴(kuò)展，他允許一個(gè)節(jié)點(diǎn)有多于2個(gè)的元素。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+樹是對(duì)B樹的一種變形樹，它與B樹的差異在于：

有k個(gè)子結(jié)點(diǎn)的結(jié)點(diǎn)必然有k個(gè)關(guān)鍵碼；
非葉結(jié)點(diǎn)僅具有索引作用，跟記錄有關(guān)的信息均存放在葉結(jié)點(diǎn)中。
樹的所有葉結(jié)點(diǎn)構(gòu)成一個(gè)有序鏈表，可以按照關(guān)鍵碼排序的次序遍歷全部記錄。

B和B+樹的區(qū)別在于，B+樹的非葉子結(jié)點(diǎn)只包含導(dǎo)航信息，不包含實(shí)際的值，所有的葉子結(jié)點(diǎn)和相連的節(jié)點(diǎn)使用鏈表相連，便于區(qū)間查找和遍歷。

但是B樹也有優(yōu)點(diǎn)，其優(yōu)點(diǎn)在于，由于B樹的每一個(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等中。

樹表查找總結(jié)：

二叉查找樹平均查找性能不錯(cuò)，為O(logn)，但是最壞情況會(huì)退化為O(n)。在二叉查找樹的基礎(chǔ)上進(jìn)行優(yōu)化，我們可以使用平衡查找樹。平衡查找樹中的2-3查找樹，這種數(shù)據(jù)結(jié)構(gòu)在插入之后能夠進(jìn)行自平衡操作，從而保證了樹的高度在一定的范圍內(nèi)進(jìn)而能夠保證最壞情況下的時(shí)間復(fù)雜度。但是2-3查找樹實(shí)現(xiàn)起來(lái)比較困難，紅黑樹是2-3樹的一種簡(jiǎn)單高效的實(shí)現(xiàn)，他巧妙地使用顏色標(biāo)記來(lái)替代2-3樹中比較難處理的3-node節(jié)點(diǎn)問(wèn)題。紅黑樹是一種比較高效的平衡查找樹，應(yīng)用非常廣泛，很多編程語(yǔ)言的內(nèi)部實(shí)現(xiàn)都或多或少的采用了紅黑樹。

除此之外，2-3查找樹的另一個(gè)擴(kuò)展——B/B+平衡樹，在文件系統(tǒng)和數(shù)據(jù)庫(kù)系統(tǒng)中有著廣泛的應(yīng)用。

6. 分塊查找

解釋：https://blog.csdn.net/u013036274/article/details/49176027

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

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

算法思想：

將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表）。