折半查找效率淺析

方瑞英?武俊芳

摘 要：折半查找法是效率較高的一種查找方法，它要求查找表是順序存儲的有序表。折半查找法特別適用于那種一經(jīng)建立就很少改動、而又經(jīng)常需要查找的線性表。 本文以12個記錄為例，分析了折半查找法過程中判定樹的形成，并詳細(xì)地研究了查找成功時和查找失敗時的ASL。

關(guān)鍵詞：折半查找法；判定樹；ASL

The Analysis of The Efficiency of The Binary Search Method

Fang Rui Ying Wu Jun Fang

Wanfang College of Science & Technology HPU

Abstract： The binary search method is an efficient search method and requires that the lookup table is an ordered list of sequential storage. The binary search method is particularly applicable to that by establishing a few changes and often need to find the linear form. This article takes 12 records as an example，analyzes the formation of the decision tree in the process of the binary search method and studies ASL of the success of the search and the failure of the search in detail.

Key Words： the binary search method； the decision tree； ASL

查找，也可稱檢索，是在大量的數(shù)據(jù)元素中找到某個特定的數(shù)據(jù)元素而進(jìn)行的工作。查找是一種操作，查找的目的在于從一些數(shù)據(jù)中尋找一個特定的值，這看似簡單的工作之所以產(chǎn)生了形形色色的各種方法，無非都是為了追求更高的效率與更方便的操作。 在范圍較小的時候，無論采取什么方法查找，所花費的時間都相差無幾，在這種情況下，算法上簡單易行，且對存儲格式要求較低的靜態(tài)查找無疑就可以滿足我們的要求。靜態(tài)查找是指對查找表只做查詢某個“特定的”數(shù)據(jù)元素是否在查找表中或檢索某個“特定的”數(shù)據(jù)元素的各種屬性的“查找”操作，它可以有不同的表示方法，在不同的表示方法中，實現(xiàn)查找操作的方法也不同。對靜態(tài)查找表可以用順序表或線性鏈表進(jìn)行表示，也可組織成有序的順序表，或者是索引順序表，相應(yīng)的查找方法可采用順序查找方法、折半查找方法和索引順序查找的方法。討論有關(guān)靜態(tài)查找表的折半查找，并計算和分析查找成功時和查找失敗時的平均查找長度。如果數(shù)列原來是有序的， 則最常用的方法是折半查找法， 也稱為二分法查找。

一、折半查找

折半查找法的基本思想是（設(shè)R[low..high]是當(dāng)前的查找區(qū)間）：首先確定該區(qū)間的中點位置；然后將待查的K值與R[mid].key比較：若相等，則查找成功并返回此位置，否則須確定新的查找區(qū)間，繼續(xù)二分查找，具體方法如下：

若r[mid].key>K，則由表的有序性可知r[mid..n].key均大于K，因此若表中存在關(guān)鍵字等于K的結(jié)點，則該結(jié)點必定是在位置mid左邊的子表r[1..mid-1]中，故新的查找區(qū)間是左子表r[1..mid-1]。

若r[mid].key

因此，從初始的查找區(qū)間r[1..n]開始，每經(jīng)過一次與當(dāng)前查找區(qū)間的中點位置上的結(jié)點關(guān)鍵字的比較，就可確定查找是否成功，失敗則當(dāng)前的查找區(qū)間就縮小一半。這一過程重復(fù)直至找到關(guān)鍵字為K的結(jié)點，或者直至當(dāng)前的查找區(qū)間為空（即查找失?。r為止。

假設(shè)有已經(jīng)按照從小到大的順序排列好的十二個整數(shù)a1～a12，要查找的數(shù)是X，其基本思想是： 設(shè)查找數(shù)據(jù)的范圍下限為low=1，上限為high=12，求中點mid=（low+high）/2，用X與中點元素mid比較，若X等于mid，即找到，停止查找；否則，若X大于mid，替換下限low=mid+1，到下半段繼續(xù)查找；若X小于mid，換上限high=mid-1，到上半段繼續(xù)查找；如此重復(fù)前面的過程直到找到或者low>high為止。如果low>high，說明沒有此數(shù)。

二、折半查找判定樹

判定樹的形態(tài)只與表結(jié)點個數(shù)n相關(guān)，而與輸入實例中r[1..n].key的取值無關(guān)。從折半查找法的過程看，以有序表的中間記錄作為比較對象，并以中間記錄將表分割為兩個子表，對子表繼續(xù)上述操作。所以，對表中每個記錄的查找過程，可用二叉樹來描述，二叉樹中的每個結(jié)點對應(yīng)有序表中的一個記錄，結(jié)點中的值為該表再表中的位置，通常稱這個描述折半查找過程的二叉樹為折半查找判定樹。

長度為n的折半查找判定樹的構(gòu)造方法為：當(dāng)n=0時，折半查找判定樹為空；當(dāng)n>0時，折半查找判定樹的跟結(jié)點是有序表中序號為mid=（n+1）/2的記錄，根結(jié)點的左子樹是與有序表r～r[mid-1]相對應(yīng)的折半查找判定樹，根結(jié)點的右子樹是與 r[mid+1]～r[n]相對應(yīng)的折半查找判定樹。

例如，長度為12的折半查找判定樹的具體生成過程為：在長度為12的有序表中進(jìn)行折半查找，不論查找哪個記錄，都必須先和中間記錄進(jìn)行比較，而中間記錄的序號為（1+12）/2=6（注意是整除即向下取整），即判定樹的根結(jié)點是6，如圖1（a）所示；考慮判定樹的左子樹，即將查找區(qū)間調(diào)整到左半?yún)^(qū)，此時的查找區(qū)間是[1，5]，也就是說，左分支上為根結(jié)點的值減1，代表查找區(qū)間的高端high，此時，根結(jié)點的左孩子是（1+5）/2=3，如圖1（b）所示；考慮判定樹的右子樹，即將查找區(qū)間調(diào)整到右半?yún)^(qū)，此的查找區(qū)間是[7，12]，也就是說，右分支上為根結(jié)點的值加1，代表查找區(qū)間的高端low，此時，根結(jié)點的右孩子是（7+12）/2=9，如圖1（c）所示；重復(fù)第二步第三步，依次確定每個結(jié)點的左右孩子，如圖1（d）所示。

這個判定樹與霍夫曼樹的區(qū)別在于折半查找的判定樹的內(nèi)節(jié)點也是待查找元素，而葉子節(jié)點是區(qū)間。因此折半查找與BST更相似，只不過折半查找的判定樹是固定的，不是動態(tài)結(jié)構(gòu)。另一個區(qū)別在于折半查找是以元素的序號來區(qū)分的，而BST的元素序號與其位置沒有關(guān)系，BST元素的鍵值決定了其位置，而且鍵值沒有二分關(guān)系。

三、折半查找法效率分析

先看{1，16，21，35，46，58，62，76，80，98，120，180}12個元素的查找表的具體例子。 從上述查找過程可知：找到第⑥個元素僅需比較1次；找到第③和第⑨個元素需比較2次；找到第①、④、⑦和⑩個元素需比較3次；找到第②、⑤、⑧…需比較4次。這個查找過程可用圖1（d）所示的二叉樹來描述。樹中每個結(jié)點表示表中一個記錄，結(jié)點中的值為該記錄在表中的位置，通常稱這個描述查找過程的二叉樹為判定樹，從判定樹上可見，查找35的過程恰好是走了一條從根到結(jié)點④的路徑，和給定值進(jìn)行比較的關(guān)鍵字個數(shù)為該路徑上的結(jié)點數(shù)或結(jié)點④在判定樹上的層次數(shù)。因此，折半查找法在成功時進(jìn)行比較的關(guān)鍵字個數(shù)最多不超過樹的深度，依此類推，可得等概率情況下查找成功時的ASL為

接下來討論失敗的情況， 在折半查找判定樹中，查找失敗時的比較次數(shù)即是查找相應(yīng)外結(jié)點時與內(nèi)結(jié)點的比較次數(shù)。如果在圖1（d）所示的判定樹中所有結(jié)點的空指針域上加一個指向一個方形結(jié)點的指針，形成如圖1（e）所示，并且稱這些方形結(jié)點為判定樹的外部結(jié)點（與之相對，稱那些圓形結(jié)點為判定樹的內(nèi)部結(jié)點），那么折半查找時查找失敗的過程就是走了一條從根結(jié)點到外部結(jié)點的路徑，和給定值進(jìn)行比較的關(guān)鍵字個數(shù)等于該路徑上內(nèi)部結(jié)點個數(shù)。例如，查找25的過程即為走了一條從根到外部結(jié)點的路徑，比較3次失敗；查找180的過程即為走了一條從根到外部結(jié)點的路徑，比較4次失敗。這樣的外部結(jié)點共有13個，因此可得等概率情況下查找失敗時的ASL為

折半查找判定樹是一棵二叉排序樹，折半查找判定樹中的內(nèi)結(jié)點都是查找成功的情況，所有外部結(jié)點是查找失敗的情況。

四、結(jié)語

雖然折半查找法的效率高，但是要將表按關(guān)鍵字排序。而排序本身是一種很費時的運(yùn)算。既使采用高效率的排序方法也要花費O（nlgn）的時間。折半查找只適用順序存儲結(jié)構(gòu)，為保持表的有序性，在順序結(jié)構(gòu)里插入和刪除都必須移動大量的結(jié)點。因此，折半查找特別適用于那種一經(jīng)建立就很少改動、而又經(jīng)常需要查找的線性表。 本文以12個記錄為例，分析了折半查找法過程中形成的判定樹，并詳細(xì)地分析了查找成功時和查找失敗時的ASL。

參考文獻(xiàn)：

[1] 嚴(yán)蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)（C語言版）[M].北京：清華大學(xué)出版社，1998.

[2] 方鋮.一種改進(jìn)的折半查找算法[J]. 現(xiàn)代電子技術(shù). 2008（05）.

[3] 魏少涵.折半查找算法在最優(yōu)化問題中的應(yīng)用[J]. 計算機(jī)時代. 2012（09）.

[4] 時百勝.基于概念的折半查找算法[J]. 計算機(jī)科學(xué). 2009（06）.

[5] 鄒國霞，唐建清.索引折半查找算法的研究與設(shè)計[J]. 計算機(jī)時代. 2009（12） .

[6] 孫義欣.用C#實現(xiàn)折半查找算法的可視化演示[J]. 電腦知識與技術(shù). 2011（29）.

[7] 柳海燕.基于C#的折半查找算法動態(tài)演示程序[J]. 電腦知識與技術(shù). 2011（23）.

[8] 王鋼，徐紅主編.數(shù)據(jù)結(jié)構(gòu)[M]. 清華大學(xué)出版社， 2005.