本文的整理基于：http://blog.csdn.net/qq_23217629/article/details/52517741

查找定義：根據(jù)給定的某個(gè)值庆械，在查找表中確定一個(gè)其關(guān)鍵字等于給定值的數(shù)據(jù)元素（或記錄）焕窝。

查找算法分類：

1）靜態(tài)查找和動(dòng)態(tài)查找；

注：靜態(tài)或者動(dòng)態(tài)都是針對(duì)查找表而言的唬滑。動(dòng)態(tài)表指查找表中有刪除和插入操作的表。

2）無序查找和有序查找棺弊。

無序查找：被查找數(shù)列有序無序均可晶密；

有序查找：被查找數(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)比較過的次數(shù)畜侦。

1. 順序查找

說明：順序查找適合于存儲(chǔ)結(jié)構(gòu)為順序存儲(chǔ)或鏈接存儲(chǔ)的線性表元扔。

基本思想：順序查找也稱為線形查找，屬于無序查找算法旋膳。從數(shù)據(jù)結(jié)構(gòu)線形表的一端開始澎语，順序掃描，依次將掃描到的結(jié)點(diǎn)關(guān)鍵字與給定值k相比較验懊，若相等則表示查找成功擅羞；若掃描結(jié)束仍沒有找到關(guān)鍵字等于k的結(jié)點(diǎn)，表示查找失敗义图。

復(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)垄懂。

2. 二分查找

說明：元素必須是有序的骑晶，如果是無序的則要先進(jìn)行排序操作。

基本思想：也稱為是折半查找草慧，屬于有序查找算法桶蛔。用給定值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)；

注：時(shí)間復(fù)雜度的求法俺祠。這個(gè)時(shí)間復(fù)雜度其實(shí)就是求迭代了多少次公给。可知蜘渣，n個(gè)元素淌铐，最糟糕的情況就是不斷的對(duì)半分n/2, n/4, ..., n/2^k(其中k就是循環(huán)的次數(shù))。

因?yàn)閚/2^k >= 1, 令n/2^k = 1,則k= log2n蔫缸，即為時(shí)間復(fù)雜度腿准。

注：折半查找的前提條件是需要有序表順序存儲(chǔ)，對(duì)于靜態(tài)查找表拾碌，一次排序后不再變化吐葱，折半查找能得到不錯(cuò)的效率。但對(duì)于需要頻繁執(zhí)行插入或刪除操作的數(shù)據(jù)集來說倦沧，維護(hù)有序的排序會(huì)帶來不小的工作量唇撬，那就不建議使用≌谷冢——《大話數(shù)據(jù)結(jié)構(gòu)》

3.? 插值查找

在介紹插值查找之前窖认，首先考慮一個(gè)新問題，為什么上述算法一定要是折半告希，而不是折四分之一或者折更多呢扑浸？

打個(gè)比方，在英文字典里面查“apple”燕偶，你下意識(shí)翻開字典是翻前面的書頁還是后面的書頁呢喝噪？如果再讓你查“zoo”，你又怎么查指么？很顯然榴鼎，這里你絕對(duì)不會(huì)是從中間開始查起晚唇，而是有一定目的的往前或往后翻。

同樣的哩陕，比如要在取值范圍1 ~ 10000 之間 100 個(gè)元素從小到大均勻分布的數(shù)組中查找5平项， 我們自然會(huì)考慮從數(shù)組下標(biāo)較小的開始查找悍及。

經(jīng)過以上分析，折半查找這種查找方式心赶，不是自適應(yīng)的（也就是說是傻瓜式的）扣讼。二分查找中查找點(diǎn)計(jì)算如下：

mid=(low+high)/2, 可寫成mid=(2*low+high-low)/2, 即mid=low+1/2*(high-low);

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

mid=low+(key-a[low])/(a[high]-a[low])*(high-low)园担，其中l(wèi)ow最小元素的下標(biāo)，high是最大元素的下表，a[high]是最大元素的值,a[low]是最小元素的值,key是待查找元素的值湖雹。所以這個(gè)方法就是用(key-a[low])/(a[high]-a[low])這個(gè)自適應(yīng)的比例來代替1/2摔吏。根據(jù)關(guān)鍵字在整個(gè)有序表中所處的位置，讓mid值的變化更靠近關(guān)鍵字key征讲，這樣也就間接地減少了比較次數(shù)诗箍。

基本思想：基于二分查找算法，將查找點(diǎn)的選擇改進(jìn)為自適應(yīng)選擇筷狼，可以提高查找效率匠童。當(dāng)然，差值查找也屬于有序查找俏险。

注：對(duì)于表長(zhǎng)較大，而關(guān)鍵字分布又比較均勻的查找表來說裤唠，插值查找算法的平均性能比折半查找要好的多预鬓。反之，數(shù)組中如果分布非常不均勻劈彪，那么插值查找未必是很合適的選擇顶猜。

復(fù)雜度分析：查找成功或者失敗的時(shí)間復(fù)雜度均為O(log2(log2n))长窄。

4. 斐波那契查找

斐波那契數(shù)列，又稱黃金分割數(shù)列疮绷，指的是這樣一個(gè)數(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ù)列越往后相鄰的兩個(gè)數(shù)的比值越趨向于黃金比例值（0.618）。

斐波那契查找就是在二分查找的基礎(chǔ)上根據(jù)斐波那契數(shù)列進(jìn)行分割的驶俊。在斐波那契數(shù)列找一個(gè)等于略大于查找表中元素個(gè)數(shù)的數(shù)F[n]饼酿，將原查找表擴(kuò)展為長(zhǎng)度為F[n](如果要補(bǔ)充元素胚膊，則補(bǔ)充重復(fù)最后一個(gè)元素，直到滿足F[n]個(gè)元素)药版，完成后進(jìn)行斐波那契分割喻犁，即F[n]個(gè)元素分割為前半部分F[n-1]個(gè)元素株汉，后半部分F[n-2]個(gè)元素歌殃，找出要查找的元素在那一部分并遞歸，直到找到路召。

對(duì)于斐波那契數(shù)列：1波材、1廷区、2、3埠帕、5、8叁巨、13呐籽、21狡蝶、34、55悬包、89……（也可以從0開始）馍乙，前后兩個(gè)數(shù)字的比值隨著數(shù)列的增加丝格，越來越接近黃金比值0.618。比如這里的89预伺，把它想象成整個(gè)有序表的元素個(gè)數(shù)曼尊，而89是由前面的兩個(gè)斐波那契數(shù)34和55相加之后的和骆撇，也就是說把元素個(gè)數(shù)為89的有序表分成由前55個(gè)數(shù)據(jù)元素組成的前半段和由后34個(gè)數(shù)據(jù)元素組成的后半段，那么前半段元素個(gè)數(shù)和整個(gè)有序表長(zhǎng)度的比值就接近黃金比值0.618肴裙，假如要查找的元素在前半段涌乳，那么繼續(xù)按照斐波那契數(shù)列來看夕晓，55 = 34 + 21，所以繼續(xù)把前半段分成前34個(gè)數(shù)據(jù)元素的前半段和后21個(gè)元素的后半段烤惊，繼續(xù)查找，如此反復(fù)渡贾，直到查找成功或失敗雄右，這樣就把斐波那契數(shù)列應(yīng)用到查找算法中了擂仍。

從圖中可以看出逢渔，當(dāng)有序表的元素個(gè)數(shù)不是斐波那契數(shù)列中的某個(gè)數(shù)字時(shí)，需要把有序表的元素個(gè)數(shù)長(zhǎng)度補(bǔ)齊智厌，讓它成為斐波那契數(shù)列中的一個(gè)數(shù)值盲赊，當(dāng)然把原有序表截?cái)嗫隙ㄊ遣豢赡艿陌ⅲ蝗贿€怎么查找。然后圖中標(biāo)識(shí)每次取斐波那契數(shù)列中的某個(gè)值時(shí)(F[k])合溺，都會(huì)進(jìn)行-1操作缀台，這是因?yàn)橛行虮頂?shù)組位序從0開始的将硝，純粹是為了迎合位序從0開始屏镊。

斐波那契查找的時(shí)間復(fù)雜度還是O(log2n)而芥，但是與折半查找相比，斐波那契查找的優(yōu)點(diǎn)是它只涉及加法和減法運(yùn)算误辑，而不用除法，而除法比加減法要占用更多的時(shí)間翘狱，因此砰苍，斐波那契查找的運(yùn)行時(shí)間理論上比折半查找小赚导，但是還是得視具體情況而定。

注：

二分法查找的mid=low+1/2*(high-low);

斐波那契查找的mid=low+F(k-1)-1;

所以將乘除法轉(zhuǎn)化為了加減法凰锡。

5. ?樹表查找

5.1 二叉樹查找

基本思想：二叉查找樹是先對(duì)待查找的數(shù)據(jù)進(jìn)行生成樹掂为，確保樹的左分支的值小于右分支的值厂置，然后在就行和每個(gè)節(jié)點(diǎn)的父節(jié)點(diǎ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ù)列芒篷。

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

下圖為二叉樹查找和順序查找以及二分查找性能的對(duì)比圖：

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

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還要大翠语。

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

2-3查找樹能保證在插入元素之后能保持樹的平衡狀態(tài)肌括，最壞情況下即所有的子節(jié)點(diǎn)都是2-node酣难，樹的高度為lgn憨募，從而保證了最壞情況下的時(shí)間復(fù)雜度。但是2-3樹實(shí)現(xiàn)起來比較復(fù)雜珠漂，于是就有了一種簡(jiǎn)單實(shí)現(xiàn)2-3樹的數(shù)據(jù)結(jié)構(gòu)媳危，即紅黑樹（Red-Black Tree）冈敛。

基本思想：紅黑樹的思想就是對(duì)2-3查找樹進(jìn)行編碼抓谴，尤其是對(duì)2-3查找樹中的3-nodes節(jié)點(diǎn)添加額外的信息。紅黑樹中將節(jié)點(diǎn)之間的鏈接分為兩種不同類型仰泻，紅色鏈接我纪，他用來鏈接兩個(gè)2-nodes節(jié)點(diǎn)來表示一個(gè)3-nodes節(jié)點(diǎn)浅悉。黑色鏈接用來鏈接普通的2-3節(jié)點(diǎn)券犁。特別的粘衬，使用紅色鏈接的兩個(gè)2-nodes來表示一個(gè)3-nodes節(jié)點(diǎn)稚新，并且向左傾斜，即一個(gè)2-node是另一個(gè)2-node的左子節(jié)點(diǎn)飞醉。這種做法的好處是查找的時(shí)候不用做任何修改缅帘，和普通的二叉查找樹相同难衰。

6. 分塊查找

算法思想：將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. 哈希查找

哈希查找是通過計(jì)算數(shù)據(jù)元素的存儲(chǔ)地址進(jìn)行查找的一種方法屯碴。O(1)的查找描睦，即所謂的秒殺。哈希查找的本質(zhì)是先將數(shù)據(jù)映射成它的哈希值导而。哈希查找的核心是構(gòu)造一個(gè)哈希函數(shù)忱叭，它將原來直觀、整潔的數(shù)據(jù)映射為看上去似乎是隨機(jī)的一些整數(shù)今艺。

哈希查找的操作步驟：

1)用給定的哈希函數(shù)構(gòu)造哈希表韵丑；

2)根據(jù)選擇的沖突處理方法解決地址沖突；

3)在哈希表的基礎(chǔ)上執(zhí)行哈希查找洼滚。

建立哈希表操作步驟：

1)step1取數(shù)據(jù)元素的關(guān)鍵字key，計(jì)算其哈希函數(shù)值（地址）遥巴。若該地址對(duì)應(yīng)的存儲(chǔ)空間還沒有被占用千康，則將該元素存入；否則執(zhí)行step2解決沖突铲掐。

2)step2根據(jù)選擇的沖突處理方法拾弃，計(jì)算關(guān)鍵字key的下一個(gè)存儲(chǔ)地址。若下一個(gè)存儲(chǔ)地址仍被占用摆霉，則繼續(xù)執(zhí)行step2豪椿，直到找到能用的存儲(chǔ)地址為止。

哈希查找步驟為：

1)Step1對(duì)給定k值携栋，計(jì)算哈希地址Di=H（k）搭盾；若HST為空，則查找失斖裰А鸯隅；若HST=k，則查找成功向挖；否則蝌以，執(zhí)行step2（處理沖突）炕舵。

2)Step2重復(fù)計(jì)算處理沖突的下一個(gè)存儲(chǔ)地址Dk=R（Dk-1），直到HST[Dk]為空跟畅，或HST[Dk]=k為止咽筋。若HST[Dk]=K，則查找成功徊件，否則查找失敗奸攻。

比如說：”5“是一個(gè)要保存的數(shù)，然后我丟給哈希函數(shù)虱痕，哈希函數(shù)給我返回一個(gè)”2"舞箍，那么此時(shí)的”5“和“2”就建立一種對(duì)應(yīng)關(guān)系，這種關(guān)系就是所謂的“哈希關(guān)系”皆疹，在實(shí)際應(yīng)用中也就形成了”2“是key，”5“是value占拍。

那么有的朋友就會(huì)問如何做哈希略就，首先做哈希必須要遵守兩點(diǎn)原則：

①: key盡可能的分散，也就是我丟一個(gè)“6”和“5”給你晃酒，你都返回一個(gè)“2”表牢，那么這樣的哈希函數(shù)不盡完美。

②：哈希函數(shù)盡可能的簡(jiǎn)單贝次，也就是說丟一個(gè)“6”給你崔兴，你哈希函數(shù)要搞1小時(shí)才能給我，這樣也是不好的蛔翅。

其實(shí)常用的做哈希的手法有“五種”：

第一種：”直接定址法“敲茄。

很容易理解，key=Value+C山析；這個(gè)“C"是常量堰燎。Value+C其實(shí)就是一個(gè)簡(jiǎn)單的哈希函數(shù)。

第二種：“除法取余法”笋轨。

很容易理解秆剪，key=value%C;解釋同上。

第三種：“數(shù)字分析法”爵政。

這種蠻有意思仅讽，比如有一組value1=112233，value2=112633钾挟，value3=119033洁灵，

針對(duì)這樣的數(shù)我們分析數(shù)中間兩個(gè)數(shù)比較波動(dòng)，其他數(shù)不變等龙。那么我們?nèi)ey的值就可以是

key1=22,key2=26,key3=90处渣。

第四種：“平方取中法”伶贰。此處忽略，見名識(shí)意罐栈。

第五種：“折疊法”黍衙。

這種蠻有意思,比如value=135790，要求key是2位數(shù)的散列值荠诬。那么我們將value變?yōu)?3+57+90=160琅翻，然后去掉高位“1”,此時(shí)key=60，哈哈柑贞，這就是他們的哈希關(guān)系方椎，這樣做的目的就是key與每一位value都相關(guān)，來做到“散列地址”盡可能分散的目地钧嘶。

影響哈希查找效率的一個(gè)重要因素是哈希函數(shù)本身棠众。當(dāng)兩個(gè)不同的數(shù)據(jù)元素的哈希值相同時(shí)，就會(huì)發(fā)生沖突有决。為減少發(fā)生沖突的可能性闸拿，哈希函數(shù)應(yīng)該將數(shù)據(jù)盡可能分散地映射到哈希表的每一個(gè)表項(xiàng)中。

解決沖突的方法有以下兩種：

(1)開放地址法

如果兩個(gè)數(shù)據(jù)元素的哈希值相同书幕，則在哈希表中為后插入的數(shù)據(jù)元素另外選擇一個(gè)表項(xiàng)新荤。當(dāng)程序查找哈希表時(shí)，如果沒有在第一個(gè)對(duì)應(yīng)的哈希表項(xiàng)中找到符合查找要求的數(shù)據(jù)元素台汇，程序就會(huì)繼續(xù)往后查找苛骨，直到找到一個(gè)符合查找要求的數(shù)據(jù)元素，或者遇到一個(gè)空的表項(xiàng)苟呐。

(2)鏈地址法

將哈希值相同的數(shù)據(jù)元素存放在一個(gè)鏈表中痒芝，在查找哈希表的過程中，當(dāng)查找到這個(gè)鏈表時(shí)牵素，必須采用線性查找方法吼野。