折半查找效率淺析

方瑞英?武俊芳

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

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

一、折半查找

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

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

若r[mid].key

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

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

二、折半查找判定樹(shù)

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

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

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

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

三、折半查找法效率分析

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

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

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

四、結(jié)語(yǔ)

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

參考文獻(xiàn)：

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

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

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

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

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

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

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

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