基于结点群的高效的动态二分查找器

计算机科学 ›› 2013, Vol. 40 ›› Issue (7): 244-247.

基于结点群的高效的动态二分查找器

张朝霞,韩素青,亓慧

太原师范学院计算机系太原030012;太原师范学院计算机系太原030012;太原师范学院计算机系太原030012

出版日期:2018-11-16 发布日期:2018-11-16
基金资助:
本文受国家自然科学基金项目(61273294),山西省教育厅高校科技开发项目(20121108),山西省科技厅基础条件平台项目(2012091003-0104)资助

Highly Efficient and Dynamic Binary Searcher Based on Node Group

ZHANG Zhao-xia,HAN Su-qing and QI Hui

Online:2018-11-16 Published:2018-11-16

摘要/Abstract

摘要： 通过对几种改进的二分查找算法的分析和总结,提出了一种基于结点群的更为高效的动态二分查找器。该二分查找器不仅使查找效率得以提高,而且使存储结构得以改进,既实现了动态的实时查找,又便于灵活地进行元素尤其是元素群的插入、删除等操作。另外,实验表明,当在大量数据中查找时,该算法明显优于以前改进的所有二分查找算法。

关键词: 二分查找,Fibonacci查找,改进的类Fibonacci查找,动态二分查找器中图法分类号TP311文献标识码A

Abstract: Based on the analysis and summary of several improved binary search algorithm,we put forward a more highlyefficient and dynamic binary searcher based on node group,which is not only improved in the search efficiency,but alsoin the storage structure．This algorithm has achieved the dynamic real-time search,and it especially allows to insert and delete a group of elements．In addition,we discovered that the scheme is obviously better than the previous binary search algorithm in searching a large amount of data.

Key words: Binary search,Fibonacci search,Improved Fibonacci search,Dynamic binary searcher

张朝霞,韩素青,亓慧. 基于结点群的高效的动态二分查找器[J]. 计算机科学, 2013, 40(7): 244-247. https://doi.org/

ZHANG Zhao-xia,HAN Su-qing and QI Hui. Highly Efficient and Dynamic Binary Searcher Based on Node Group[J]. Computer Science, 2013, 40(7): 244-247. https://doi.org/

参考文献

[1] Knuth D E．The Art of Computer Programming,3:Sorting and Searching [M]．Addison Wesley,1973
[2] 严蔚敏,吴伟民.数据结构(C语言版)[M].北京:清华大学出版社,2007:220-222,238-239
[3] iamhaiyang.二分查找学习札记.http://blog.chinaunix.net/uid-544794-id-2097252.html,2012-02-20
[4] 詹炜,等.一种基于Fibonacci数的有序线性表查找算法[J].电脑开发与应用,2005,18(12):29
[5] 陈启星,罗启宇．分档定位排序以及向分档定位查找的发展[J].计算机研究与发展,2003,40(5):706
[6] 陈启星,陈彬,陈叶．用静态链表和逆序插入算法构成的动态查找表[J]．电脑与信息技术,2007,15(3):2-3
[7] 长春工业大学.数据结构精品课程[M].线性表的查找技术之斐波那契查找,2011
[8] 周德苏,李光明.对Fibonacci静态查找算法的改进[J].空军雷达学院学报,2000,14(3):45-47
[9] 罗南超,蹇旭,崔丽.一种改进的新二分查找算法的研究与实现[J].计算机时代,2009,205(7):56
[10] 一道笔试题:用最快速度查出有序数组中的一个数．http://www.khgl.cn/html/38/n-4z76038.html,2012

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed