温馨提示×

温馨提示×

您好,登录后才能下订单哦!

密码登录×
登录注册×
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》

Java二分查找方法如何使用

发布时间:2021-12-30 09:38:00 来源:亿速云 阅读:206 作者:iii 栏目:大数据

这篇文章主要介绍“Java二分查找方法如何使用”,在日常操作中,相信很多人在Java二分查找方法如何使用问题上存在疑惑,小编查阅了各式资料,整理出简单好用的操作方法,希望对大家解答”Java二分查找方法如何使用”的疑惑有所帮助!接下来,请跟着小编一起来学习吧!

功能:排行榜

需求:按积分给前端返回一个有序集合,为0不显示,并给出当前用户排名位置

实现:

  1. 计算出所有用户(包含当前用户的)积分集合

  2. 过滤掉为0的,且按分数倒序排列,分数越高排名越前

  3. 再把当前用户信息找到,判断其在集合中的位置

方案一:List.indexOf(object)

源码

 public int indexOf(Object o) {        if (o == null) {            for (int i = 0; i < size; i++)                if (elementData[i]==null)                    return i;        } else {            for (int i = 0; i < size; i++)                if (o.equals(elementData[i]))                    return i;        }        list不包含返回-1        return -1;    }

底层就是遍历判断元素相当则返回元素位置,下标从0开始,所以结果需要+1。

当前方案不能解决问题吗?

能,通过逻辑判断可不用contains判断是否在集合内。

能解决问题那二分查找哪来的?

第一:indexOf底层的遍历如果极端情况下,10000用户,恰好当前用户排在第10000个,那效率太低。

方案二   二分查找  Collections.binarySearch

  Tuning parameters for algorithms  优化算法  public static <T>    int binarySearch(List<? extends Comparable<? super T>> list, T key) {        if (list instanceof RandomAccess || list.size()<BINARYSEARCH_THRESHOLD)            return Collections.indexedBinarySearch(list, key);        else            return Collections.iteratorBinarySearch(list, key);    }

阈值为5000

private static final int BINARYSEARCH_THRESHOLD   = 5000;

二分查找源代码

 private static <T>    int indexedBinarySearch(List<? extends Comparable<? super T>> list, T key) {        int low = 0;        int high = list.size()-1;
       while (low <= high) {            int mid = (low + high) >>> 1;            Comparable<? super T> midVal = list.get(mid);            int cmp = midVal.compareTo(key);
           if (cmp < 0)                low = mid + 1;            else if (cmp > 0)                high = mid - 1;            else                return mid; // key found        }        return -(low + 1);  // key not found    }

如何测试效率?集合中放10万数据去测试下indexOf和binarySearch即可

 public static void main(String[] args) {        List<Integer> list = new ArrayList<>();        for (int i = 0; i < 100000; i++) {            list.add(i);        }
       long time = System.currentTimeMillis();        list.indexOf(58645);        System.out.println("indexOf耗时:");        System.out.println(System.currentTimeMillis()-time);        long binarySearchtime = System.currentTimeMillis();        Collections.binarySearch(list,58645);        System.out.println("二分查找耗时:");        System.out.println(System.currentTimeMillis()-binarySearchtime);    }indexOf耗时:13二分查找耗时:1

性能提升13倍

到此,关于“Java二分查找方法如何使用”的学习就结束了,希望能够解决大家的疑惑。理论与实践的搭配能更好的帮助大家学习,快去试试吧!若想继续学习更多相关知识,请继续关注亿速云网站,小编会继续努力为大家带来更多实用的文章!

向AI问一下细节

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

AI