一:概論
查找,或搜索(Search),是最頻繁的操作,基礎(chǔ)中的基礎(chǔ).
查找表(search table):也就是指在一個(gè)容器中查找目標(biāo)內(nèi)容,所有的內(nèi)容(數(shù)據(jù)元素)構(gòu)成的集合就是查找表.
關(guān)鍵字(key):key這里是指數(shù)據(jù)元素的某個(gè)數(shù)據(jù)項(xiàng)(字段)的值,鍵值,而不是字段本身,它可能唯一的標(biāo)識(shí)著一個(gè)元素,叫做主關(guān)鍵字,也就是每一條數(shù)據(jù)的主關(guān)鍵字都不相同,而這個(gè)值對(duì)應(yīng)的字段就是主鍵.
靜態(tài)查找表:只做查找操作
動(dòng)態(tài)查找表:查找,插入,刪除操作
查找是從集合中找到目標(biāo)數(shù)據(jù),一般來(lái)說(shuō),集合中的數(shù)據(jù)直接并沒(méi)什么關(guān)系,比如一個(gè)普通的訂單表,每條數(shù)據(jù)之間沒(méi)有相關(guān)性,但是想要提升查找的性能,就需要把集合組織成表,樹(shù)等結(jié)構(gòu),利用數(shù)據(jù)結(jié)構(gòu)的特性來(lái)提升查找效率.
二:順序表查找
如果你想從一堆散亂堆砌的書(shū)中找到一本想要的書(shū),這是你會(huì)考慮先把這堆書(shū)排列整齊,然后從第一本按順序查找.
這個(gè)過(guò)程就是把集合組織成線(xiàn)性表,然后從線(xiàn)性表的第一個(gè)元素開(kāi)始對(duì)比,叫做順序查找,是最基本的查找方式.
如果用代碼實(shí)現(xiàn),那就是遍歷線(xiàn)性表
當(dāng)然也可以?xún)?yōu)化一下,不使用for循環(huán)遍歷,省去每次對(duì)比i是否<=n的過(guò)程
顯然順序表查找的復(fù)雜度O(n).
三:有序表查找
還是找書(shū)的例子,如果隨便把書(shū)擺在書(shū)架上,那么查找只能從第一本開(kāi)始,如果按照書(shū)名首字拼音來(lái)擺好,那么直接跳到對(duì)應(yīng)的位置開(kāi)始找就行了
這就是對(duì)集合根據(jù)一個(gè)或多個(gè)key來(lái)進(jìn)行有序排列,組織成一個(gè)有序的線(xiàn)性表.
1.二分查找
二分查找,或者折半查找,很容易理解,首先要是有序線(xiàn)性表.
比如在[0,1,16,24,35,47,59,62,73,88,99]中查找62,這是個(gè)簡(jiǎn)化的例子,這些數(shù)字是復(fù)雜數(shù)據(jù)的一個(gè)關(guān)鍵字,它的意義在于找到62然后訪(fǎng)問(wèn)這條數(shù)據(jù)的具體信息.
在下面的例子中,都不考慮下標(biāo)0,0的位置放一個(gè)數(shù)值0,最小下標(biāo)從1開(kāi)始
代碼實(shí)現(xiàn)如下,low和high表示當(dāng)前要查找的范圍,也就是記錄折半折到哪了,注釋基本寫(xiě)的很詳細(xì).
過(guò)程很好理解關(guān)鍵是復(fù)雜度的分析,把二分查找繪制成二叉樹(shù),發(fā)現(xiàn)這個(gè)例子中的查找,就是其中一條路徑,根據(jù)n個(gè)節(jié)點(diǎn)的完全二叉樹(shù)深度是log?n + 1,那么二分查找的復(fù)雜度就是O(logn).
2.插值查找
回到找書(shū)的例子,在把書(shū)按順序擺好之后,二分法就沒(méi)必要了,如果是找博物雜志,你會(huì)知道在靠前的位置,如果是找趙氏孤兒,你會(huì)知道到靠后的位置找,如果轉(zhuǎn)換成數(shù)學(xué)問(wèn)題,那就類(lèi)似于從0-10000中找88和9900.
插值查找其實(shí)只需要把二分查找稍微改變一下就行.
這里需要用到插值公式mid = low + (key - a[low]) / (a[high] - a[low]) * (high - low),這是個(gè)數(shù)學(xué)問(wèn)題,歸納自上面講到的例子,從每次取中間作為mid,變成按照比例來(lái)計(jì)算mid,原先mid先=5,現(xiàn)在mid先=2(取整),發(fā)現(xiàn)a[2]就是16,直接就找到了
從時(shí)間復(fù)雜度來(lái)看,差值查找也是O(n),屬于是對(duì)二分查找的優(yōu)化.
3.斐波那契查找
斐波那契查找也類(lèi)似于插值查找,是利用斐波那契數(shù)列;
算法代碼:
分析:
數(shù)組a=[0,1,1,16,24,35,47,59,62,73,88,99],需要查找是值是59,數(shù)組F是斐波那契數(shù)列;
兩個(gè)指針low和high,從0和n開(kāi)始,第6~8行,得到k= 7;
第9~10行是為了補(bǔ)全數(shù)組,后面有用;
第13行,mid = 1+F[7-1]-1 = 8,也就是從下標(biāo)8開(kāi)始;
此時(shí)key = 59,a[8] = 63,16~17行得到high = 7;key = 6;
經(jīng)過(guò)幾次循環(huán)得到a[6] = key;
當(dāng)key<a[mid]時(shí),新的查找范圍是low到mid-1,此時(shí)范圍內(nèi)個(gè)數(shù)是F[k-1]-1個(gè),
當(dāng)k>a[mid]時(shí),新的查找范圍是mid到high,個(gè)數(shù)是F[k-2]-1個(gè);
斐波那契查找的復(fù)雜度也是O(nlogn),但是對(duì)于處在中間的大部分?jǐn)?shù)據(jù),效率比插值查找更高;
另外斐波那契查找僅需要加法運(yùn)算,折半和插值需要四則運(yùn)算,對(duì)于巨量的數(shù)據(jù)來(lái)說(shuō),效率也有提升.
