一种改进的二分查找算法

一种改进的二分查找算法 21 南邹国霞,何 ( 1 、桂林航天工业高等专科学校 计算机系 ,广西桂林 541004 ; ) 2 、桂林师范高等专科学校 物理与信息技术系 ,广西桂林 541004 摘 要 :当前在有序数列查找中二分查找最为常用 ,但是二分查找在一些特殊情况下 ,其查找效率很低 ,如查找元素是数 列中的第一个元素和最后一个元素 。针对这种情况 ,结合数列特性 ,设计了一种改进的二分查找算法 。改进的二分查找 n + 1n + 1 ( ) 算法经理论和实验 证明 住所证明下载场所使用证明下载诊断证明下载住所证明下载爱问住所证明下载爱问 ,其平均查找长度介于 1 和 lo gn + 1? 1 之间 , 明显优于二分查找的平均查找长度 lo g2 2n n ( ) n + 1? 1 ,实现难度比参考文献[ 1 ]要容易 。 关键词 :二分查找 ;平均查找长度 ;有序数列 ;等差数列 ;算法 ( ) 文章编号 :167227800 20100320053202 中图分类号 : T P301 . 6文献标识码 : A 05 lo w - st ep = 0 ; 06 high - st ep = 0 ; 0 引言( () () ( ) )07 while low < = high& &low - step > = 0& &high - st ep > = 0 08 { 数列查找常用的算法有顺序查找算法、二分算法、索引查() ( ) 09 lo w - st ep = i nt x - A [ lo w ] / d ; 找算法、分块查找、二叉排序树、散列查找。其中对有序序列采 10 lo wt e mp = lo w ; 用的查找算法二分算法性能最好。但是二分查找在特殊情况 10 lo w = lo w + lo w - st ep ; 下效性很低 ,比如 ,当要查找的 A [ 1 . . 17 ] = 1 ,4 ,5 ,7 ,8 , 9 , 10 , ( ) 11 if A [ lo w ] > xlo w = lo wt e mp ; 12 ,15 ,18 ,19 ,22 ,24 , 27 ,30 ,32 ,35 中的 1 时 ,二分查找要找 5( ) 12 if A [ lo w ] = = xret ur n lo w ; 次 ,如果用顺序查找 , 则只需要查找 1 次。因此在某种特殊情 () ( ) 13 high - st ep = i nt A [ high ] - x/ d ; 况下二分查找比较低效。为此本文设计并证明了一种改进的 14 hight e mp = high ; 15 high = high - high - st ep ; 二分查找算法 ,其设计 思想 教师资格思想品德鉴定表下载浅论红楼梦的主题思想员工思想动态调查问卷论语教育思想学生思想教育讲话稿 如下。 ( ) if A [ hi gh ] < xhigh = hight e mp ; 16 ( ) if A [ hi gh ] = = xret ur n hi gh ; 17 1 改进的二分查找算法() () mi d = i nt lo w + hi gh/ 2 ; 13 ( )if x = = A [ mid ] 14 { ret ur n mid ;} 15 1 . 1 算法思想 由于二分查找总是将元素由一部分分为两部分 ,其思想具 ( )el se if x < A [ mi d ] 16 有简洁性 ,但是在某些情况下 ,还不是很高效。经研究发现 ,在 high = mid - 1 ; 17 充分利用二分查找算法的基础上 ,可以利用数列的特性来加大 el se 18 对数据筛选的速度 ,其思想如下 : lo w = mi d + 1 ; 19 虽然数据序列不是等差数列 ,但是我们可以等效为等差数} 20 ret ur n 0 ; 21 列来看待 ,这样就可以缩短查找长度 ,设序列为 a1 ,a2 ,a n , } 22 ( ) ( ) 可以求得等差为 d = ceil A [ n ] - A [ 1 ]/ n - 1; 其中 ceil 用来 其中第 7 行用来结束查找 ,当 lo w < = high 时 ,说明在整个 取上整的 ,其算法如下 :序列中找不到该元素 ;lo w - st ep > = 0 ,用来提前结束查找 , 当 ( )i nt Imp ro vedBi nar ySea rch A r ray A ,i nt n , Ele ment x 查找的元素比要查找的序列中的最小元素还要小时 ,说明该元 01 { i nt lo w , high ,i ndex ,lo w - st ep ,lo wt e mp , high - st ep , hight e mp , 素不存在。同理 ,high - st ep > = 0 , 说明查找的元素比要查找 d ; 的序列中的最大元素还要大 ,说明该元素也不存在。 02 lo w = lo wt emp = 1 ; 第9 、1 2 行是用来筛选元素的 , 将用于二分查找的序列范03 high = hight e mp = n ; ( ) ( ) d = ceil A [ n ] - A [ 1 ] / n - 1; / / ceil 用来取上整的 04 第 11 、15 行用来控制跨度太大 ,将要查找的元素给过滤掉1 。找长度为 如果要查找值为 x 的元a n , 了 ,遇到这种情况就退回到二分查找的初始位置。设等差数列 A 为 a1 , a2 , 1 . 2 算法实例 分析 定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析 素 , 根据改进二分查找算法 , 分以下 4 种情况讨论 : 1 . 2 . 1 查找元素在序列中 ( ) 1 x 在数列中 例 1 假设要从如下数组中查找 x = 35 的元素() ( ) d = a n - a1/ n - 1; A [ 1 . . 17 ] = 1 , 4 , 5 , 7 , 8 , 9 , 10 , 12 , 15 , 18 , 19 , 22 , 24 , 27 , 设 a m = x ,则根据改进二分查找算法有如下结果 : 30 ,32 ,35 ( ) () lo w - st ep = x - a1/ d = a m - a1/ d = m - 1 ; ( ) 根据改进的二分法查找 ,步长 d = 「A [ 17 ] - A [ 1 ]/ 16 =( ) lo w = lo w - st ep + lo w = 1 + m - 1= m ; () 「35 - 1/ 16」= 3 。 ?A [ m ] = a m ; ?找到元素 ,返回结果为 lo w 的值 ,即 m .第 1 轮 其平均查找长度为 1 。 ( ) () ()35 - 1/ 3 = 11 ; 2 x 不在数列中 ,且 a1 < x < a nlo w - st ep = 「x - A [ 1 ]/ d」= lo w = 1 + 11 = 12 ; 设 A [ m ] < x < A [ m + 1 ] , 则根据改进二分查找算法有如A [ lo w ] = 22 ; 下结果 : ( ) () lo w - st ep = x - a1/ d = a m - a1/ d = m - 1 ; ?A [ lo w ] < 35 ; ?lo w = 12 ; ( ) () ( ) high - st ep = A [ 17 ] - x/ d = 35 - 35/ 3 = 0 ; lo w = lo w - st ep + lo w = 1 + m - 1= m ; () high = 17 ; high - st ep = a n - x/ d = n - m ; high = m ; ?A [ high ] = 35 ; ?返回结果 17 ; 因此 ,改进的二分查找算法只需要一轮 , 就可以找到要查 ?A [ high ] < A [ m ] ; 找的元素 ,如果采用传统二分查找算法 , 需要查找 5 轮才能找 ?A [ high ] < x ,循环结束 ,返回结果为 0 ,说明查找不成功。 () 到结果 ,而参考文献[ 1 ]里需要用 2 轮查找。3 x 不在数列中 ,且 x < a1 1 . 2 . 2 查找元素不在序列中设 a m = x ,则根据改进二分查找算法有如下结果 : ( ) () 例 3 假设要从上述数组中查找 x = 11 的元素 ,序列不存在 lo w - st ep = x - a1/ d = a m - a1/ d < 0 ; 循环结 此元素。 束 ,返回结果为 0 ,说明查找不成功。 ()x 不在数列中 ,且 x > a n 4 第 1 轮 lo w - st ep = 3 ;lo w = 4 ; A [ lo w ] = 7 < 11 ; high - st ep = 8 ; 设 a m = x ,则根据改进二分查找算法有如下结果 : () hi gh = 9 ; A [ high ] = 15 > 11 ; high - st ep = a n - x/ d < 0 ; 循环结束 ,返回结果为 0 ,说明查找不成功。 综合上面的此时数列为 7 ,8 ,9 ,10 ,12 ,15 共 6 个元素 证明得知 ,当数据序列为等差数列时 ,其平均查 mid = 6 ; A [ mid ] = 9 < 11 ; ?利用二分查找 ,lo w = 6 , high = 9 ; 找长度为 1 。当不为等差数列时 ,从算法里可以看出 ,其退化到 最差情况就是 low 和 high 退化到传统二分查找情况。因此该改 第 2 轮 ( ) 进的二分查找算法平均查找长度介于 1 和 n + 1 nlog2 n + 1? 1 元素序列为 9 ,10 ,12 ,15 共 4 个元素 ( ) lo w - st ep = 0 ;lo w = 6 ; A [ lo w ] = 9 ; 之间 , 而二分查找的平均查找长度 n + 1 nlog2 n + 1? 1 。 high - st ep = 1 ; high = 8 ; A [ high ] = 12 ; 3 实验验证 此时数列为 9 ,10 ,12 共 3 个元素 实验 1 使用的数据是随机产生的 1000 个元素 ,然后对元素 mid = 7 ; A [ mid ] = 10 < 11 ; lo w = 7 ; 进行升序排序 ;实验 2 使用的是等差为 1 的 10000 个顺序数据。 程 序 中 采 用 Q uer y Perfo r ma nce Frequency 和 Q uer y Perfo r2 第 3 轮 元素序列为 10 ,12 ,15 共 3 个元素ma nceCo unt er 来计算算法执行的时间 ,时间单位为秒 , 精确到 lo w - st ep = 0 ;lo w = 7 ; A [ lo w ] = 10 ; 了微妙。其实验对比分析图分别如图 1 、2 所示。 high - step = 1 ;high = 7 ;A[high] = 10 < 11 循环结束 ,返回结果为 0 , 说明没有找到元素。如果用传统二分查找需要比较 5 轮。 2 改进二分查找算法性能分析 n + 1定理 : 改进的二分查找算法平均查找长度介于 1 和 n ( ) lo gn + 1- 1 之间 。2 图 1 1000 个随机元素查找时间趋势图 由于该改进算法采用近似等差数列性质原理 , 因此 , 该改 使用 C # 语言实现层次分析法算法模型 1 2 高 鹏,李学军 () 1 . 中国人民解放军通信指挥学院 ,湖北 武汉 430010 ;2 . 中国电子系统工程公司研究所 ,北京 100039 随着社会的发展 ,系统在生活中的作用越来越重要 ,如何对系统效能进行评估成为一个重要课题 。在介绍层次分 摘 要 : 析法基本原理的基础上 ,利用 C # 语言对其算法模型进行了实现 ,对效能评估方法在实践中的应用进行了介绍 。 关键词 :效能评估 ;层次分析法 ; C # 语言 ( ) 文章编号 :167227800 20100320055202 中图分类号 : T P301 . 6文献标识码 : A 0 1 引言层次分析法基本概念 ( ) 近年来 ,随着社会的发展 , 系统的概念已经深入到人类生A nal ytic Hierarchy Proce ss ,简称 A H P是美层次分析法 活的各个角落 ,例如城市交通系统、公共安全应急系统、公民医 国匹兹堡大学教授 Saat y T. L 于上世纪 70 年代中期提出的一 疗保障系统等。系统的特点是体系化、规模化 , 其组成结构复 种系统分析方法。是一种将定性分析和定量计算相结合的分 杂、组成要素多样 ,相互间影响关系也较为综合。与之对应 ,对 析方法 ,是分析多目标、多准则复杂系统的有力工具。它是一 系统效能进行评估 ,优化其体系结构 , 元素组成的理论方法日 种将决策者对复杂系统的决策思维过程模型化、数量化的过 益受到人们的重视“, 以评估促发展”已经成为国内外专家的一程。应用这种方法 ,决策者通过将复杂问题分解为若干层次和 致共识。若干因素 ,在各因素之间进行简单的比较和计算 , 就可以得出 目前用于效能评估的方法较多 ,较常用的主要有层次分析 不同 方案 气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载 的权重 ,为最佳方案的选择提供依据。 法、模糊综合评判法、ADC 法、指数法、S EA 方法等。本文以层 分析的基本步骤为 : ?明确问题 : 弄清问题的范围 ,涉及因 次分析法为例 ,在介绍层次分析法基本概念的基础上 , 对使用 素 ,各因素间的关系等 ; ?建立层次关系 : 将问题所含的因素进 C # 语言实现其算法模型的具体方法进行说明。 行分组 ,建立层次关系 ; ?构造判断矩阵 : 评定层次中各有关元 参考文献 : ( ) [ 1 ] 王海涛 ,朱洪. 改进的二分法查找[J ] . 计算机工程 ,2006 5.( ) 李根强. 数据结构 C + + 描述[ M ] . 北京 : 中国水利水电出版社 , [ 2 ] 2005 . 黄刘生 , 唐策善. 数据结构 [ M ] . 合肥 : 中国科学技术大学出版社 , [ 3 ] 2002 . Gup t a , V . A Keywo r d Searchi ng Al go rit h m Fo r Sea rch Engi ne s[ C ] . 图 2 10000 数据等差序列查找时间趋势图[ 4 ] Inno vatio n s i n Info r matio n Technolo gy , 2007 . Inno vatio n s ’ 07 . 4t h ( ) Int er natio nal Co nf erence o n . 18220 No v. 2007 Page s:2032207 . 4 结束语J u Hyo ung Mun . Bi na r y sea rch o n p refi x lengt h s fo r IP addre ss loo k2 [ 5 ] up [ C ] . Co mmunicatio n s L et t er s , I EE E Vol u me 10 , Issue 6 , J une 本文依据二分查找算法的思想 , 结合数列特性 , 增加了步( ) 2006 Page s: 4922494 . 长参数来对序列进行数据筛选 , 筛选完后再实行二分查找 , 当 Agar , A . U . Allebach , J . P . Mo del2ba sed colo r half to ni ng usi ng di2 [ 6 ] 序列数据元素比较多时 ,可以大大提高查找效率。在文中对该 rect bi na r y sea rch [ C ] . Image Proce ssi ng , I EE E Tra n sactio n s o n . Vol2 ( ) 改进的二分查找算法进行了理论证明和实验分析 ,其结果证明u me 14 , Issue 12 , Dec . 2005 Page s:194521959 . ( )责任编辑 :卓 光 该改进的二分查找算法是可行的 ,并能提高二分查找效率。 () ( ) 作者简介 :高鹏 19782,男 ,河北保定人 ,中国人民解放军通信指挥学院硕士研究生 ,研究方向为系统仿真 、效能评估 ;李学军 19692,男 ,