二分查找的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)
blank

相关推荐

  • UML类图介绍

    UML类图介绍文章目录UML类图一、类图概述二、类图的作用三、类图表示法1.类的表示方式2.类与类之间关系的表示方式2.1关联关系2.2聚合关系2.3组合关系2.4依赖关系2.5继承关系2.6实现关系UML类图一、类图概述类图显示了模型中存在的类、类的内部结构以及它们与其他类的关系二、类图的作用类图描述了系统的类的集合,类的属性和类之间的关系,可以简化了人们对系统的理解三、类图表示法1.类的表示方式在UML类图中,类使用包含类名、属性和方法且带有分割线的矩形来表示比如下图表示一个Emp

  • linux系统 系统推荐 deepin国产系统 最好用的国产linux系统 Windows系统的优秀替代品 deepin系统安装 系统安装 deepin[通俗易懂]

    linux系统 系统推荐 deepin国产系统 最好用的国产linux系统 Windows系统的优秀替代品 deepin系统安装 系统安装 deepin[通俗易懂]前言:我用过多款linux系统,电脑上装的是Ubuntu和deepin,服务器端用的是centos,还用过优麒麟等。黑苹果也用了一段时间。现在linux系统已经发展的比较完善,内核及其图形界面也很稳定,当要说真的可以当做个人操作系统来使用的,我认为是deepin系统。deepin是一款国产系统,基于debian开发的linux操作系统,它拥有linux系统的所有优势,而且完美结合deepin-…

  • jquery+正則表達式验证邮箱格式的样例「建议收藏」

    jquery+正則表達式验证邮箱格式的样例

  • 常用dos命令(八)–COPY命令

    常用dos命令(八)–COPY命令今天的是copy(复制)命令,说起这个命令,也许你没使用过这个命令,但是平常生活与工作中总会长期用到ctrl+c和ctrl+v这两个功能吧。下面是几个小例子:1、将桌面的hello.txt文件复制到d盘:c:\Users\DT236\Desktop>copyhello.txtd:2、将多个文件合并在一个文件里面:c:\Users\DT236\Desktop>copyh

  • IT培训行业揭秘(一)

    IT培训行业揭秘(一)前言:闲扯淡IT培训行业的各种你不知道的事情!

  • Reactor模式详解

    Reactor模式详解在学习Reactor模式之前,我们需要对“I/O的四种模型”以及“什么是I/O多路复用”进行简单的介绍,因为Reactor是一个使用了同步非阻塞的I/O多路复用机制的模式。I/O的四种模型I/0

发表回复

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

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