一種改進的折半查找算法

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

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

中圖分類號：TP391 文獻標識碼：B

文章編號：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 引 言

查找是計算機科學中的一項復(fù)雜技術(shù)，二分法查找又叫折半查找，對于順序存儲的有序表的查找，二分法查找是一種簡單、常用的查找方法，且當每個對象的查找概率相等時，二分法查找的性能是最優(yōu)的。

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

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

2 算法思想

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

3 算法分析

3.1 查找長度分析

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

直接對子表進行折半查找，平均查找長度為^[1]：

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

3.2 存儲量分析

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

4 結(jié) 語

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

參考文獻

［1］D.E.克努特.計算程序設(shè)計方法學[M].管紀文，蘇運霖，譯.北京：國防科技出版社，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虛擬機內(nèi)存管理分析[J].現(xiàn)代電子技術(shù)，2007，30(5):172-174.

作者簡介

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

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