摘 要：針對(duì)查找范圍變化很大而又相對(duì)穩(wěn)定的查找對(duì)象，給出了一種改進(jìn)的基于區(qū)間控制的折半查找算法，當(dāng)后一個(gè)查找對(duì)象在前一個(gè)查找對(duì)象附近時(shí)，在最壞狀態(tài)和平均狀態(tài)下，該算法與傳統(tǒng)的標(biāo)準(zhǔn)折半查找算法相比，其查找長度顯著減少，查找速度快，當(dāng)父表很大而子表相對(duì)很小時(shí)，存儲(chǔ)上僅需增加一個(gè)額外的存儲(chǔ)單元，實(shí)現(xiàn)代價(jià)很小。此算法適用于過程控制中的實(shí)時(shí)查找處理，有一定的實(shí)用價(jià)值。

關(guān)鍵詞：折半查找；查找長度；區(qū)間控制；過程控制

中圖分類號(hào)：TP391 文獻(xiàn)標(biāo)識(shí)碼：B

文章編號(hào)：1004373X(2008)0516302

A Binary Search Based on Range Restaint

FANG Cheng

(Wuhan Polytechnic University，Wuhan，430023，China)

Abstract：Aiming at stable search object，a modified binary search algorithm is given in this paper.When the ordered list is long and the item to be accessed is near the prior one，the new algorithm with very little cost gives much less path length than the old one under the worst condition and the average condition.This algorithm is useful for real-time searching in the area of process contro1.

Keywords：binary search;search lenth;range restraint;process control

1 引 言

查找是計(jì)算機(jī)科學(xué)中的一項(xiàng)復(fù)雜技術(shù)，二分法查找又叫折半查找，對(duì)于順序存儲(chǔ)的有序表的查找，二分法查找是一種簡單、常用的查找方法，且當(dāng)每個(gè)對(duì)象的查找概率相等時(shí)，二分法查找的性能是最優(yōu)的。

Huffman D.對(duì)概率不相等的查找問題給出了一個(gè)精巧的算法^[1]。人們對(duì)不同的問題，對(duì)標(biāo)準(zhǔn)的折半查找算法進(jìn)行某種不同程度的修改，以期得到更好的應(yīng)用效果。

本文提出的在區(qū)間控制下的折半查找算法是對(duì)傳統(tǒng)折半查找算法的一種改進(jìn)，其方法簡單有效，代價(jià)小，查找速度快。

2 算法思想

設(shè)r[1..N]為一有序表，稱之為父表，表中有N個(gè)記錄，且關(guān)鍵字按升序排列，即有r[i+1].key>r[i].key，i=1，2，……，N-1。第j次被查找的記錄在父表中的序號(hào)為ij，ij=1，2，……N，j=1，2，……。對(duì)于任意j，若存在有約束條件：

3 算法分析

3.1 查找長度分析

假定每次查找都成功。設(shè)父表的記錄個(gè)數(shù)N=2H-1，子表的記錄個(gè)數(shù)為n=2h-1，H和h都為正整數(shù)(這種假設(shè)對(duì)查找長度的影響很小^[2])；Tx為父表中第x個(gè)記錄的查找長度，x=1，2……，N；ty為子表中第y個(gè)記錄的查找長度，y=1，2，……，n。設(shè)任一個(gè)子表r[ij-(n-1)/2..ij+(n-1)/2]中的每一個(gè)節(jié)點(diǎn)的查找概率為1/n。

直接對(duì)子表進(jìn)行折半查找，平均查找長度為^[1]：

在等概率查找條件下，改進(jìn)了的查找算法與傳統(tǒng)的折半算法相比，查找長度有所改善。例如：當(dāng)N=65 535，n=15時(shí)，查找長度是原算法長度的1/5，節(jié)省80%。

3.2 存儲(chǔ)量分析

改進(jìn)的算法在作區(qū)間初值時(shí)要作一次加法和減法運(yùn)算，當(dāng)父表很大，子表相對(duì)很小時(shí)此種開銷可以忽略，存儲(chǔ)量僅增加一個(gè)存放單元。應(yīng)該指出，改進(jìn)的算法在具體實(shí)現(xiàn)時(shí)要處理好父表兩端的情況，否則容易出現(xiàn)錯(cuò)誤。

4 結(jié) 語

本文提出的算法是對(duì)傳統(tǒng)二分法算法的改進(jìn)，其方法簡單有效，而且代價(jià)很小。當(dāng)父表很大，子表相對(duì)很小時(shí)，新算法的時(shí)間效率將大幅度提高，他適合用于查找范圍變化很大而又相對(duì)穩(wěn)定的查找對(duì)象。

參考文獻(xiàn)

［1］D.E.克努特.計(jì)算程序設(shè)計(jì)方法學(xué)[M].管紀(jì)文，蘇運(yùn)霖，譯.北京：國防科技出版社，1980.

［2］Yosi Ben-Asher，Eitan Farchi，Ilan Newman.Optimal Search in Trees[J].SIMA Journal on Computing，1999，28(6):2 090-2 102.

［3］王凌飛，王保保.Java虛擬機(jī)內(nèi)存管理分析[J].現(xiàn)代電子技術(shù)，2007，30(5):172-174.

作者簡介

方 鋮 男，1974年出生，湖北武漢人，講師。

注：“本文中所涉及到的圖表、注解、公式等內(nèi)容請(qǐng)以PDF格式閱讀原文。”