二分查找的Java实现「建议收藏」

目录写在前面二分查找的原理代码实现学习感想写在前面二分查找是一个很有趣的算法,可以很大程度的提升性能,比如待查询的数组或其他集合很大的时候,二分查找的威力就可以体现出来。但是平时的工作中我们基本上不会去写二分查找,所以我觉得有必要写一篇博文来记录二分查找的学习。二分查找的原理所谓二分查找,其实就是获取一组有序数据的中间数据,判断其跟查询关键字的…

大家好,又见面了,我是你们的朋友全栈君。

目录

写在前面

二分查找是一个很有趣的算法,可以很大程度的提升性能,比如待查询的数组或其他集合很大的时候,二分查找的威力就可以体现出来。但是平时的工作中我们基本上不会去写二分查找,所以我觉得有必要写一篇博文来记录二分查找的学习。

二分查找的原理

所谓二分查找,其实就是获取一组有序数据的中间数据,判断其跟查询关键字的大小,然后得到新的查找区间,继续重复以上的操作,直到最后查询区间不存在或者查询到关键字的下标。这样说起来可能还是有点抽象。So,Talk is cheap, Show me the code!

代码实现

/** * Author : Ray * Created At : 2018-03-13 下午8:41 * Email : ryu18356@gmail.com * Description : 二分查找的实例程序 */
public class BinarySearchDemo { 
   

    /** * 二分查找key值对应的下标 * @param source 输入的源数组 ,请保证为一个有序数组 * @param key 需要查找的值 * @return 正数为查找到的坐标,-1表示没有查到 */
    public static int binarySearch(int[] source, int key) {
        int low = 0;
        int high = source.length - 1;
        while (low <= high) {
            int mid = ( low + high ) >>> 1; //使用位移运算法高效地获取折中下标,这里不考虑符号,所以使用>>>
            int midVal = source[mid];
            if ( midVal < key ) {
                low = mid + 1;
            } else if ( midVal > key ) {
                high = mid - 1;
            }  else
                return  mid;
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] source = new int[]{
  
  12,213,232,343,123,-1,123,232424,1253,56,456,234,-2342};
        //保证数组为有序数组
        Arrays.sort(source);
        //打印排序后的数组元素
        System.out.print("Sorted Source : ");
        for (int i = 0; i < source.length; i++) {
            System.out.print(source[i] + " ");
        }
        System.out.println();
        System.out.println(binarySearch(source, 56));
    }

}

最后的运行效果为下图
result

学习感想

其实如果对Java SDK的源码熟悉的话,会一眼看出上面的二分查找其实就是仿写的Arrays.java的binarySearch方法,下面是源码的二分查找

 // Like public version, but without range checks.
    private static int binarySearch0(int[] a, int fromIndex, int toIndex,
                                     int key) {
        int low = fromIndex;
        int high = toIndex - 1;

        while (low <= high) {
            int mid = (low + high) >>> 1;
            int midVal = a[mid];

            if (midVal < key)
                low = mid + 1;
            else if (midVal > key)
                high = mid - 1;
            else
                return mid; // key found
        }
        return -(low + 1);  // key not found.
    }

可以看出我们最上面的例子其实就是借鉴Java源码的,Arrays类提供了很多便捷高效的方法,比如sort排序等。最后说一下,二分查找这种我们平时并不会写出来用,因为SDK已经给我们提供了实现。但是我们应该在空闲时间多多关注一下Java源码的实现,毕竟这些都是编程届的巨人们的思想结晶。我们可以通过源码学习很多知识,比如数据结构与算法,设计模式,面向对象编程技巧等,我坚信大多数大牛们之所以牛,就是因为源码读的多,写得多。当然那种天马行空的天才除外!所以,作为平凡人的我们应该掌握一些缩短我们与大牛差距的学习技巧,不要让好的学习资源((ps: 开车我是拒绝的!哈哈:))安静地待在我们的硬盘里。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/129501.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • [分享]在线的代码片段测试工具 jsbin[通俗易懂]

    [分享]在线的代码片段测试工具 jsbin[通俗易懂]有些时候,我们往往有这样的需求:临时测试一个代码片段,不想打开编辑器来新建一个文件,测试完毕又删除想给别人分享一个代码,html文件,css文件,js文件,打个包?向别人展个某个效果,发个文件过去?把代码部署到自己服务器上面?针对这些需求,我们使用在线的代码片段测试工具,也许来得更加简单和方便了。针对前端的在线代码片段工具很多,比较常见的有jsbin和jsfiddle以及codepen.而我最喜欢的就是jsbin了,它有着更多的特性给我带来了极大的方便:任意控制要展示的窗口点击这些标

    2022年10月25日
  • Extjs grid设置单元格字体颜色,单元格背景颜色,行背景颜色

    Extjs grid设置单元格字体颜色,单元格背景颜色,行背景颜色Extjsgrid设置单元格字体颜色,单元格背景颜色,行背景颜色 一.在ColumnModel中用renderer渲染颜色:1.不定义样式:(1).字体颜色:{ header:"审核状态", dataIndex:"status", width:100, renderer:function(v){ if(v==1){ return"&lt;s…

  • iconfont的使用方法

    iconfont的使用方法一、iconfont的使用登录http://www.iconfont.cn/阿里巴巴矢量图标库,github或微博登录 选择喜欢的图标添加入库 然后点击右侧购物车,点击最下面的‘下载代码’按钮,下载保存到本地,解压即可得到需要的文件 有三种方法使用(1)unicode引用unicode是字体在网页端最原始的应用方式,特点是:兼容性最好,支持ie6+,及所有现代浏览器。 支持…

    2022年10月26日
  • ewebeditor漏洞大全

    ewebeditor漏洞大全1:默认管理后台: http://www.backlion.com/ewebeditor/admin_login.asp后台如果能进入:可点击样式管理:standard拷贝一份(直接修改改不了)在拷贝的一份里加入图片类型(asaaaspsp)  然后点预览在编辑器里点设计   然后直接上传asa大马.上传后在代码里可以看到马的位置!

  • pycharm激活码 2022.01.13_最新在线免费激活

    (pycharm激活码 2022.01.13)最近有小伙伴私信我,问我这边有没有免费的intellijIdea的激活码,然后我将全栈君台教程分享给他了。激活成功之后他一直表示感谢,哈哈~IntelliJ2021最新激活注册码,破解教程可免费永久激活,亲测有效,下面是详细链接哦~https://javaforall.cn/100143.html…

  • 磁盘管理器能看到u盘,但电脑里没有_bt3安装到u盘启动不了

    磁盘管理器能看到u盘,但电脑里没有_bt3安装到u盘启动不了最近在弄bt3U盘版的时候,依照网上的方法弄了半天都有问题,一直都进不去xwindow,由于spoonwep工具是有界面的,故只在命令行下如果没有界面的支持,是不能办事的,后来在网上看到很多兄弟们说显卡的问题,结果在无线网论坛里找到了ATI卡的驱动,具体下载的地址是:http://www.wlanbbs.com/thread-5439-1-1.html  非常感谢这位提供驱动的兄弟,ATI在哪

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号