前言

本文的文字及圖片來源于網(wǎng)絡(luò),僅供學(xué)習(xí)、交流使用,不具有任何商業(yè)用途,如有問題請及時聯(lián)系我們以作處理。

PS：如有需要Python學(xué)習(xí)資料的小伙伴可以加點(diǎn)擊下方鏈接自行獲取

python免費(fèi)學(xué)習(xí)資料然磷、代碼以及交流解答點(diǎn)擊即可加入

查找算法 -- 簡介

查找（Searching）就是根據(jù)給定的某個值，在查找表中確定一個其關(guān)鍵字等于給定值的數(shù)據(jù)元素需纳。
查找表（Search Table）：由同一類型的數(shù)據(jù)元素構(gòu)成的集合
關(guān)鍵字（Key）：數(shù)據(jù)元素中某個數(shù)據(jù)項(xiàng)的值捺信，又稱為鍵值
主鍵（Primary Key）：可唯一的標(biāo)識某個數(shù)據(jù)元素或記錄的關(guān)鍵字
查找表按照操作方式可分為：
1.靜態(tài)查找表（Static Search Table）：只做查找操作的查找表。它的主要操作是：
①查詢某個“特定的”數(shù)據(jù)元素是否在表中
②檢索某個“特定的”數(shù)據(jù)元素和各種屬性

2.動態(tài)查找表（Dynamic Search Table）：在查找中同時進(jìn)行插入或刪除等操作：
①查找時插入數(shù)據(jù)
②查找時刪除數(shù)據(jù)

順序查找

算法簡介
順序查找又稱為線性查找仁烹，是一種最簡單的查找方法耸弄。適用于線性表的順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)。該算法的時間復(fù)雜度為O(n)卓缰。

基本思路
從第一個元素m開始逐個與需要查找的元素x進(jìn)行比較卸勺，當(dāng)比較到元素值相同(即m=x)時返回元素m的下標(biāo)，如果比較到最后都沒有找到摊欠，則返回-1吠式。
優(yōu)缺點(diǎn)
缺點(diǎn)：是當(dāng)n 很大時，平均查找長度較大总寒，效率低扶歪；
優(yōu)點(diǎn)：是對表中數(shù)據(jù)元素的存儲沒有要求。另外，對于線性鏈表善镰，只能進(jìn)行順序查找妹萨。
算法實(shí)現(xiàn)

二分查找

算法簡介
二分查找（Binary Search），是一種在有序數(shù)組中查找某一特定元素的查找算法炫欺。查找過程從數(shù)組的中間元素開始乎完，如果中間元素正好是要查找的元素，則查找過程結(jié)束品洛；如果某一特定元素大于或者小于中間元素树姨，則在數(shù)組大于或小于中間元素的那一半中查找，而且跟開始一樣從中間元素開始比較桥状。如果在某一步驟數(shù)組為空帽揪，則代表找不到。
這種查找算法每一次比較都使查找范圍縮小一半辅斟。
算法描述
給予一個包含 個帶值元素的數(shù)組A
1转晰、 令 L為0 ， R為 n-1
2砾肺、如果L>R挽霉，則搜索以失敗告終
3、 令 m (中間值元素)為 ?(L+R)/2?
4变汪、 如果 AmT侠坎，令 R為 m - 1 并回到步驟二
復(fù)雜度分析
時間復(fù)雜度：折半搜索每次把搜索區(qū)域減少一半，時間復(fù)雜度為 O(logn)
空間復(fù)雜度：O(1)
算法實(shí)現(xiàn)

插值查找

算法簡介
插值查找是根據(jù)要查找的關(guān)鍵字key與查找表中最大最小記錄的關(guān)鍵字比較后的 查找方法裙盾，其核心就在于插值的計(jì)算公式 (key-a[low])/(a[high]-a[low])*(high-low)实胸。
時間復(fù)雜度o(logn)但對于表長較大而關(guān)鍵字分布比較均勻的查找表來說，效率較高番官。

算法思想
基于二分查找算法庐完，將查找點(diǎn)的選擇改進(jìn)為自適應(yīng)選擇，可以提高查找效率徘熔。當(dāng)然门躯，差值查找也屬于有序查找。
注：對于表長較大酷师，而關(guān)鍵字分布又比較均勻的查找表來說讶凉，插值查找算法的平均性能比折半查找要好的多。反之山孔，數(shù)組中如果分布非常不均勻懂讯，那么插值查找未必是很合適的選擇。
復(fù)雜度分析
時間復(fù)雜性：如果元素均勻分布台颠，則O（log log n））褐望，在最壞的情況下可能需要O（n）。
空間復(fù)雜度：O（1）。

算法實(shí)現(xiàn)

斐波那契查找

算法簡介
斐波那契數(shù)列瘫里，又稱黃金分割數(shù)列实蔽，指的是這樣一個數(shù)列：1、1减宣、2盐须、3、5漆腌、8、13阶冈、21闷尿、····，在數(shù)學(xué)上女坑，斐波那契被遞歸方法如下定義：F(1)=1填具，F(xiàn)(2)=1，F(xiàn)(n)=f(n-1)+F(n-2) （n>=2）匆骗。該數(shù)列越往后相鄰的兩個數(shù)的比值越趨向于黃金比例值（0.618）劳景。
算法描述
斐波那契查找就是在二分查找的基礎(chǔ)上根據(jù)斐波那契數(shù)列進(jìn)行分割的。在斐波那契數(shù)列找一個等于略大于查找表中元素個數(shù)的數(shù)F[n]碉就，將原查找表擴(kuò)展為長度為Fn盟广，完成后進(jìn)行斐波那契分割，即F[n]個元素分割為前半部分F[n-1]個元素瓮钥，后半部分F[n-2]個元素筋量，找出要查找的元素在那一部分并遞歸，直到找到碉熄。
復(fù)雜度分析
最壞情況下桨武，時間復(fù)雜度為O(log2n)，且其期望復(fù)雜度也為O(log2n)锈津。
算法實(shí)現(xiàn)

樹表查找

1呀酸、二叉樹查找算法。
算法簡介
二叉查找樹是先對待查找的數(shù)據(jù)進(jìn)行生成樹琼梆，確保樹的左分支的值小于右分支的值性誉，然后在就行和每個節(jié)點(diǎn)的父節(jié)點(diǎn)比較大小，查找最適合的范圍叮叹。 這個算法的查找效率很高艾栋，但是如果使用這種查找方法要首先創(chuàng)建樹。

算法思想
二叉查找樹（BinarySearch 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ì)：對二叉查找樹進(jìn)行中序遍歷扣猫，即可得到有序的數(shù)列菜循。

復(fù)雜度分析
它和二分查找一樣，插入和查找的時間復(fù)雜度均為O(logn)申尤，但是在最壞的情況下仍然會有O(n)的時間復(fù)雜度癌幕。原因在于插入和刪除元素的時候，樹沒有保持平衡昧穿。

算法實(shí)現(xiàn)

2-3 查找樹的性質(zhì)
　　 1）如果中序遍歷2-3查找樹，就可以得到排好序的序列严肪；
　　 2）在一個完全平衡的2-3查找樹中史煎，根節(jié)點(diǎn)到每一個為空節(jié)點(diǎn)的距離都相同谦屑。（這也是平衡樹中“平衡”一詞的概念，根節(jié)點(diǎn)到葉節(jié)點(diǎn)的最長距離對應(yīng)于查找算法的最壞情況篇梭，而平衡樹中根節(jié)點(diǎn)到葉節(jié)點(diǎn)的距離都一樣氢橙，最壞情況也具有對數(shù)復(fù)雜度。）
復(fù)雜度分析：
　　 2-3樹的查找效率與樹的高度是息息相關(guān)的恬偷。
距離來說悍手，對于1百萬個節(jié)點(diǎn)的2-3樹，樹的高度為12-20之間袍患，對于10億個節(jié)點(diǎn)的2-3樹坦康，樹的高度為18-30之間。
　　 對于插入來說协怒，只需要常數(shù)次操作即可完成涝焙，因?yàn)樗恍枰薷呐c該節(jié)點(diǎn)關(guān)聯(lián)的節(jié)點(diǎn)即可，不需要檢查其他節(jié)點(diǎn)孕暇，所以效率和查找類似。

 B+ 樹簡介

    B+樹是B-樹的變體塞淹，也是一種多路搜索樹：
        1.其定義基本與B-樹同窟蓝，除了：
        2.非葉子結(jié)點(diǎn)的子樹指針與關(guān)鍵字個數(shù)相同；
        3.非葉子結(jié)點(diǎn)的子樹指針P[i]饱普，指向關(guān)鍵字值屬于[K[i], K[i+1])的子樹
        4.B-樹是開區(qū)間运挫；
        5.為所有葉子結(jié)點(diǎn)增加一個鏈指針；
        6.所有關(guān)鍵字都在葉子結(jié)點(diǎn)出現(xiàn)套耕；

    如：（M=3）

B+樹算法思想

    B+的搜索與B-樹也基本相同谁帕，區(qū)別是B+樹只有達(dá)到葉子結(jié)點(diǎn)才命中（B-樹可以在非葉子結(jié)點(diǎn)命中），其性能也等價于在關(guān)鍵字全集做一次二分查找箍铲；
B+樹的特性
       1.所有關(guān)鍵字都出現(xiàn)在葉子結(jié)點(diǎn)的鏈表中（稠密索引）雇卷，且鏈表中的關(guān)鍵字恰好是有序的；
       2.不可能在非葉子結(jié)點(diǎn)命中颠猴；
       3.非葉子結(jié)點(diǎn)相當(dāng)于是葉子結(jié)點(diǎn)的索引（稀疏索引）关划，葉子結(jié)點(diǎn)相當(dāng)于是存儲（關(guān)鍵字）數(shù)據(jù)的數(shù)據(jù)層；
       4.更適合文件索引系統(tǒng)翘瓮；
 算法實(shí)現(xiàn)

分塊查找

算法簡介
要求是順序表馋劈，分塊查找又稱索引順序查找攻锰，它是順序查找的一種改進(jìn)方法。

算法思想
將n個數(shù)據(jù)元素"按塊有序"劃分為m塊（m ≤ n）妓雾。
每一塊中的結(jié)點(diǎn)不必有序口注，但塊與塊之間必須"按塊有序"；
即第1塊中任一元素的關(guān)鍵字都必須小于第2塊中任一元素的關(guān)鍵字君珠；
而第2塊中任一元素又都必須小于第3塊中的任一元素，……

算法流程　
1娇斑、先選取各塊中的最大關(guān)鍵字構(gòu)成一個索引表策添；
2、查找分兩個部分：先對索引表進(jìn)行二分查找或順序查找毫缆，以確定待查記錄在哪一塊中唯竹；
3、在已確定的塊中用順序法進(jìn)行查找苦丁。
復(fù)雜度分析
時間復(fù)雜度：O(log(m)+N/m)

哈希查找

算法簡介
哈希表就是一種以鍵-值(key-indexed) 存儲數(shù)據(jù)的結(jié)構(gòu)浸颓，只要輸入待查找的值即key，即可查找到其對應(yīng)的值旺拉。

算法思想
哈希的思路很簡單产上，如果所有的鍵都是整數(shù)，那么就可以使用一個簡單的無序數(shù)組來實(shí)現(xiàn)：將鍵作為索引蛾狗，值即為其對應(yīng)的值晋涣，這樣就可以快速訪問任意鍵的值。這是對于簡單的鍵的情況沉桌，我們將其擴(kuò)展到可以處理更加復(fù)雜的類型的鍵谢鹊。

算法流程

1）用給定的哈希函數(shù)構(gòu)造哈希表算吩；
　　2）根據(jù)選擇的沖突處理方法解決地址沖突；
　　　　 常見的解決沖突的方法：拉鏈法和線性探測法佃扼。
　　3）在哈希表的基礎(chǔ)上執(zhí)行哈希查找偎巢。
復(fù)雜度分析
　　單純論查找復(fù)雜度：對于無沖突的Hash表而言，查找復(fù)雜度為O(1)（注意兼耀，在查找之前我們需要構(gòu)建相應(yīng)的Hash表）压昼。

算法實(shí)現(xiàn)