[科普中國]-外部查找

定義

查找是指在數(shù)據(jù)序列中尋找符合特定條件的數(shù)據(jù)。在計(jì)算機(jī)中，存儲器的層次結(jié)構(gòu)一般分為：CPU寄存器、主存、輔存，外部查找是指在輔助設(shè)備空間進(jìn)行數(shù)據(jù)查找。進(jìn)行外部查找的原因：

在計(jì)算機(jī)中內(nèi)存的大小是有限的， 如果要查找的數(shù)據(jù)量太大，無法全部加載到內(nèi)存中，必須借助輔助存儲設(shè)備的空間再進(jìn)行查找；2

2. 為了提高計(jì)算機(jī)處理的效率，處理更多的進(jìn)程，我們一般只加載一部分?jǐn)?shù)據(jù)，需要的再到輔存中查找。

查找方法查找方法在實(shí)際運(yùn)做過程中數(shù)據(jù)的存儲方式不同，可分為“內(nèi)部查找”與“外部查找”兩類。這里是主要是外部查找的方法。

順序查找順序查找(sequential scarch)又稱線性查找，是‘種最簡單的查找方法。它是指將數(shù)據(jù)以線性表的形式存儲，用線性表來表示靜態(tài)查找表。其基本思想是：從線性表中第一個(gè)記錄開始，依次比較每個(gè)數(shù)據(jù)元素的關(guān)鍵字，若記錄的關(guān)鍵字與給定值相等，則查找成功返回該元素序號；若查完整個(gè)線性表都沒有與給定值匹配的元素，則查找失敗。

復(fù)雜度分析：

查找成功時(shí)的平均查找長度為：（假設(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)。

折半查找二分查找又稱折半查找，優(yōu)點(diǎn)是比較次數(shù)少，查找速度快，平均性能好；其缺點(diǎn)是要求待查表為有序表，且插入刪除困難。因此，折半查找方法適用于不經(jīng)常變動(dòng)而查找頻繁的有序列表。首先，假設(shè)表中元素是按升序排列，將表中間位置記錄的關(guān)鍵字與查找關(guān)鍵字比較，如果兩者相等，則查找成功；否則利用中間位置記錄將表分成前、后兩個(gè)子表，如果中間位置記錄的關(guān)鍵字大于查找關(guān)鍵字，則進(jìn)一步查找前一子表，否則進(jìn)一步查找后一子表。重復(fù)以上過程，直到找到滿足條件的記錄，使查找成功，或直到子表不存在為止，此時(shí)查找不成功。

復(fù)雜度分析：最壞情況下，關(guān)鍵詞比較次數(shù)為log2(n+1)，且期望時(shí)間復(fù)雜度為O(log2n)；

斐波那契查找基本思想：也是二分查找的一種提升算法，通過運(yùn)用黃金比例的概念在數(shù)列中選擇查找點(diǎn)進(jìn)行查找，提高查找效率。同樣地，斐波那契查找也屬于一種有序查找算法。

相對于折半查找，一般將待比較的key值與第mid=（low+high）/2位置的元素比較，比較結(jié)果分三種情況：

1）相等，mid位置的元素即為所求

2）>，low=mid+1;

3），low=mid+1,k-=2;

說明：low=mid+1說明待查找的元素在[mid+1,high]范圍內(nèi)，k-=2 說明范圍[mid+1,high]內(nèi)的元素個(gè)數(shù)為n-(F(k-1))=Fk-1-F(k-1)=Fk-F(k-1)-1=F(k-2)-1個(gè)，所以可以遞歸的應(yīng)用斐波那契查找。

3）