第
32
卷第
10
期
Vol
.3
2
NJJ
10
计算机工程
Computer
Engineering
2006
年
5
月
岛1:a
y
2006
·软件技术与数据库·
文章编号
100
←
-3428(2006)1
。→
06
6--{)
3
文献标识码
A
申图分类号
TP312
改进的二分法查找
玉梅祷，朱拱
(复旦大学计算机科学与工程系，上海
200433)
摘要:当前有很多的查找算法，其中在对有序数列的查找算法中二分法查找
(binary
search)
是最常用的。利用二分法，在含有
n
个元素的
有序数列中查找一个元素的最大比较次数为
Llogn
J+I
0
在很多情况中，在查找之前有序数列分布的很多信息为已知，比如说如果知道了有
序数列中每相邻两个元素之差的最大值的一个上界，就可以有比二分法更加有效的查找算法。文章给出了一个称之为改进的二分法查找算
法。改进的二分法查找性能明显优于二分法查找，受数列分布的影响，其最坏情况下查找一个元素的最大比较次数在
l
和
Llog
，小
l
之间，
明显优于二分查找的
Llogn
J+I
。在实际应用中利用改进的二分法可以极大地提高查找效率。
关键词:查找;二分法;有序数列;算法
Modified Binary Search
WANG
Haitao
,
ZHU
Hong
(Department ofComputer Science and Engineering, Fudan University, Shanghai 200433)
(Abstract)
Consider the problem
of
determining whether a given elementx is
in
缸
Tay.
To
solve the
se
缸
ch
problem
，由
ere
are many algorithms.
And binary search
is
the most common search algorithm if the array is sorted. The number
of
comparisons performed by binary search
on
a
sort
巳
d
array
of
size n
is
at
mo
叫
log
n J+ 1 . The time cost
of
binary search
re
时
es
the lower bound
of
the search problem. But in many circumstances, some
information about
the
町
ay
before
se
缸
ch
is
known.
If由
e
upp
巳
r
bound of the maximum difference between any adjacent elements in
th
巳
array
lS
known, one can design a preferable algorithm. It
is
refe
盯
'ed
as modified binary search. In the worst
case
，由
e
maximum number
of
comparisons
performed by modified binary
se
缸
ch
is
between 1 and
Llogn
J+l
，
obviou
句
better
than
bin
町
S
巳缸
ch.
(Key
words)
Search; Binary search;
Sorted
町
ay;
AIgorithm
1
概述
给出一个特定的元素
x
，
在含有
n
个元素的数列
A
中
判断是否存在这个元素，如果存在，返回此元素在数列中的
位置，否则返回零。一般称这样的问题为数列查找问题。数
列查找问题在实际中用得很广，但是大多时候都是作为一个
大问题中的子问题或者作为一个程序的子程序出现。比如说
在数据库中常用到
B
树的数据结构，在
B
数的每一个内部节
点中一般都会有很多元素，在对整个
B
树的查找过程中，当
遍历到某个内部节点时就需要判断应该进入下层节点的哪一
个分支，这时候就需要在此节点的数列中查找。因此数列查
找算法的好坏直接影响到整个
B
数的操作，进而影响到数据
库的执行效率。在其它很多问题中，数列查找都是作为其中
一个基本的过程，其查找速度直接影响到整个问题执行效率。
当前，针对许多不同的情况有很多的数列查找算法。特别是，
如果数列原来是有序的，则最常用的算法是二分法查找
(Binary
Search[ll)
。利用二分法查找一个元素的最大比较次数
不超过
Llogn
J+l
，这里
n
为数列元素的个数。相比之下用顺
序查找的最大比较次数
n-l
，
其性能大为提高。
用判定树模型知道，二分法查找实际上已经达到了数列
查找问题的下界，也就是说在同样的情况下很难再设计出比
二分查找更有效的算法。因此，二分查找得到广泛应用，上
述在
B
树内部节点中的查找一般用的就是二分查找。
但是有很多情况，在对数列查找之前，我们可能已经知
道了许多数列的相关信息。比如说，如果知道了有序数列中
每相邻两个元素之差的最大值的一个上界，也就是说，设
一
-6
0-一
MAX=m
缸
2
主自
{A[i]-A
[i
-l])
，如果已知
M
，
而且
M?MAX
，
在这
种情况下本文给出了一个性能优于二分法的查找算法，由于
新的算法源于二分法查找的思想，因此称之为改进的二分法
查找。改进的二分法查找性能明显优于通常的二分法，受数
列分布情况和
M-MAX
的影响，其最坏情况下查找一个元素的
最大比较次数介于
1
和
Llogn
J+l
之间。如果数列是等差数列
而且
M=MAX
(
最好情况)，其查找一个元素的最大比较次数仅
为
1
。反之，如果对数列分布情况了解得不是很充分，得到
的
M
与
MAX
之差大于数列中最大元素与最小元素之差(最差
情况)，这时，其查找一个元素的最大比较次数为
Llogn
J+l ,
实际上退化为二分查找。因此，如果
M
与
MAX
比较接近，改
进的算法就能极大地提高查找性能。
为了便于比较，本文首先分析了通常的二分法查找，然
后给出了改进的二分法查找及其性能分析。
2
二分法查找
二分法查找的基本思想是将目标元素与数列中间的元素
比较，比较一次后如果不相等则跳过数列一半的元素，将目
标元素再与数列中剩下的元素中的中间的元素比较，这样递
基金项目:国家自然科学基金资助项目
(60496321)
;科学技术部基础
研究重大项目前期研究专项基金资助项目
(2001
CCA0300)
;上海市
科技发展基金资助项目
(025115032)
作者简介
t
王海涛(1
981
一)，男，硕士生，主研方向:算法设计与分
析，计算复杂性理论，近似算法等;朱
洪，教授
收稿日期
2005-07-23
E-mail:
wa
鸣
haita
口，
hzhu@fudan.edu.cn
下载后可阅读完整内容，剩余3页未读，立即下载
lg1163848884
- 粉丝: 0
- 资源: 5
我的内容管理
展开
最新资源
- 李兴华Java基础教程：从入门到精通
- U盘与硬盘启动安装教程：从菜鸟到专家
- C++面试宝典：动态内存管理与继承解析
- C++ STL源码深度解析：专家级剖析与关键技术
- C/C++调用DOS命令实战指南
- 神经网络补偿的多传感器航迹融合技术
- GIS中的大地坐标系与椭球体解析
- 海思Hi3515 H.264编解码处理器用户手册
- Oracle基础练习题与解答
- 谷歌地球3D建筑筛选新流程详解
- CFO与CIO携手：数据管理与企业增值的战略
- Eclipse IDE基础教程：从入门到精通
- Shell脚本专家宝典：全面学习与资源指南
- Tomcat安装指南：附带JDK配置步骤
- NA3003A电子水准仪数据格式解析与转换研究
- 自动化专业英语词汇精华：必备术语集锦
资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！
点击此处反馈
