【摘 要】
：
当前有很多的查找算法,其中在对有序数列的查找算法中二分法查找(binarysearch)是最常用的。利用二分法,在含有n个元素的有序数列中查找一个元素的最大比较次数为??logn??+1
【基金项目】
：
国家自然科学基金资助项目(60496321);科学技术部基础研究重大项目前期研究专项基金资助项目(2001CCA0300);上海市科技发展基金资助项目(025115032)
论文部分内容阅读
当前有很多的查找算法,其中在对有序数列的查找算法中二分法查找(binarysearch)是最常用的。利用二分法,在含有n个元素的有序数列中查找一个元素的最大比较次数为??logn??+1。在很多情况中,在查找之前有序数列分布的很多信息为已知,比如说如果知道了有序数列中每相邻两个元素之差的最大值的一个上界,就可以有比二分法更加有效的查找算法。文章给出了一个称之为改进的二分法查找算法。改进的二分法查找性能明显优于二分法查找,受数列分布的影响,其最坏情况下查找一个元素的最大比较次数在1和??logn??+1之间,明显优于二分查找的??logn??+1。在实际应用中利用改进的二分法可以极大地提高查找效率。
其他文献
高中班主任承载着一个学生甚至一个家庭的梦想,其素质的高低、工作方法的优劣将直接影响着学生的三年高中生活甚至他们的一生。因此如何建设一支“好”班主任队伍具有至关重
本文通过阅读大量半导体封装工艺、铜线封装、铜线封装可靠性等相关文献,结合实践工作成果,阐述了铜线封装工艺在国内外的研究现状,研究论证铜线封装在半导体封装工艺中取代
认知语篇学是认知语言学的一个分支,以语篇为研究对象,旨在通过从认知角度解释语篇的内部结构,从而将语篇的生成与理解纳入人类的一般认知模式。在语篇的性质和意义问题上,认
氧化沟由于通常采用表面曝气的方式进行供氧,造成沟中的溶解氧和流速的不均匀分布,从而对处理效果和能耗产生影响.本文根据氧化沟的水力特性,计算并比较了沟内的流速分布,按
以氯化钠作为共晶盐研究对象,探讨共晶盐反复多次的低温液-固相变后的晶体变化趋势。通过X射线衍射仪,对试样相变前后的晶体的晶面间距、粒径等参数进行分析,判断其晶体结构
前视声纳通道数目多、采样频率高,获取方位和距离信息的运算量大,对信号实时处理能力要求较高。为此,利用现场可编程门阵列(FPGA)内部运算单元以及并行分布式运算结构,对原始
大型推土机动力换挡技术是衡量推土机技术先进性的主要指标。以国产TY220推土机为例,对其液压控制换挡技术进行系统分析。结果表明:该推土机液压控制换挡操纵系统已基本具备
提出一种通过状态分配来实现有限状态机的功耗和面积同时优化的方法·在分析现有成本函数的基础上,提出了一个新的成本函数,并利用遗传算法能进行多目标优化的能力来实现功耗
<正>石榴种类很多,可大致分两类:一类是供观赏的花卉石榴;另一类供食用的果石榴。供观赏的花卉石榴又分花石榴(主要观花,花后一般不结果)和果石榴(此种石榴先花后果,但花不如
接纳控制是实现IP网络QoS最重要的手段之一,长期以来一直受到广大研究者的关注,基于不同理论的各种接纳控制机制不断出现。它们在一定程度上都能满足QoS的需求,但也在可伸缩