Binary Search二分查找算法

>> 欢迎您客人: 登录 | 注册 | 在线 | 搜索 | 风格 | 帮助 | 统计 | 文章

返回首页

>>分享数据结构和算法相关的知识和技术

书籍支持

卫琴直播

品书摘要

在线测试

资源下载

联系我们

Java技术网站 → 『 Java开发技术』 → 『数据结构和算法专题』 → Binary Search二分查找算法

您是本文章第 19929 个阅读者

* 贴子主题: Binary Search二分查找算法

点赞(0) 收藏

作者:flybird 发表时间：2020-03-15 22:58:07

消息

查看

搜索

好友

邮件

复制

引用

     1. 背景

        Binary Search(二分查找法)也称为折半查找法，用来查找一组有序记录数组中某一项记录。

       其基本思想是：将记录按有序化(递增或递减)排列

        查找过程中用跳跃式方式查找。

                2. 优点

        比较次数少

        查找速度快

        平均性能好

        占用系统内存较少

                3. 缺点

        数据源必须有序(递增或递减)

        插入删除困难

                4. 例子

     例如对于[5、10、19、21、31、37、42、48、50、52]这十个数，从中查找48这条记录，如图

点击在新窗口中浏览原图
CTRL+鼠标滚轮放大或缩小

      从图中可以看出，3次就找到了48这个数。

                    如果是顺序查找，则需要8次。

                    因此二分查找法的效率比顺序查找法要好(平均来说)。

                    顺序查找平均次数为：(1+2+3+4+5+6+7+8+9+10)/10=5.5次

                    二分查找平均次数为：(4+3+2+4+3+1+4+3+2+3)/10 = 2.9次

----------------------------
原文链接:https://blog.51cto.com/lisea/1978038

程序猿的技术大观园：www.javathinker.net

[这个贴子最后由 flybird 在 2020-03-16 11:19:09 重新编辑]

Java精品书籍推荐