java二分查找方法的实现和其优化(解决整数溢出)

简介: java二分查找方法的实现和其优化(解决整数溢出)

java二分查找方法的实现和其优化(解决整数溢出)


package cn.itcast.algorithm.suanFa;
/**
 * 二分法查找实现
 */
public class MainS11 {
    public static void main(String[] args) {
        int[] arr = {1,2,3,4,5,6,7,8,9,10};
        int target = 2;
        //创建一个二分查找方法
        int idx = erFen(arr,target);
        System.out.println(idx);
    }
    private static int erFen(int[] a, int target) {
        int l = 0,r = a.length-1,m;
        while(l < a.length){
            //未优化时:
//                  m = (l + r)/2;
            //方法一:
//                  m = l + (r - l)/2;
            //方法二:
                    m = (l + r) >>> 1;
            if (a[m] == target){
                return m;
            }else if (a[m] > target){
                r = m - 1;
            }else {
                l = m + 1;
            }
        }
        return -1;
    }
}

但是在获取中间索引m的时候,

当数组里的数值太多,且求取值在右半部分时(即 m > Integer.MAX_VALUE时)会造成溢出,此时m值为负数。

解决方法如下:

**方法一:**
    m = (l + r)/2;
    变换一下为(l/2 + r/2) --> l + (-l/2 + r/2) --> l + (r - l)/2
    ==> 最后为 m = l + (r - l)/2
**方法二:**
    用无符号的右移运算代替除法
    相比于方法一时间的更短,效率更高
    m = (l + r)/2;
    变换为---> m = (l + r) >>> 1;
 **二分查找的边界选取:**
    奇数二分去中间
    偶数二分取中间靠左
    但实际上,二分查找有许多变化,实现代码不同,左右边界的选取     可能会有变化,需要注意
目录
打赏
0
0
0
0
0
分享
相关文章
Java容器及其常用方法汇总
Java Collections框架提供了丰富的接口和实现类,用于管理和操作集合数据。
Java容器及其常用方法汇总
|
20天前
|
java语言后台管理ruoyi后台管理框架-登录提示“无效的会话,或者会话已过期,请重新登录。”-扩展知识数据库中密码加密的方法-问题如何解决-以及如何重置若依后台管理框架admin密码-优雅草卓伊凡
java语言后台管理ruoyi后台管理框架-登录提示“无效的会话,或者会话已过期,请重新登录。”-扩展知识数据库中密码加密的方法-问题如何解决-以及如何重置若依后台管理框架admin密码-优雅草卓伊凡
73 3
java语言后台管理ruoyi后台管理框架-登录提示“无效的会话,或者会话已过期,请重新登录。”-扩展知识数据库中密码加密的方法-问题如何解决-以及如何重置若依后台管理框架admin密码-优雅草卓伊凡
|
18天前
|
java.time常用方法汇总
`java.time` API 是从 Java 8 开始引入的时间日期处理库,旨在替代老旧的 `java.util.Date` 和 `Calendar`。它提供了更简洁、强大和灵活的方式处理日期、时间、时区及时间间隔,支持全球化和时间计算需求。API 包含获取当前时间、创建指定时间、解析和格式化字符串、进行加减运算、比较时间、获取年月日时分秒、计算时间间隔、时区转换以及判断闰年等功能。示例代码展示了如何使用这些功能,极大简化了开发中的时间处理任务。
Java快速入门之类、对象、方法
本文简要介绍了Java快速入门中的类、对象和方法。首先,解释了类和对象的概念,类是对象的抽象,对象是类的具体实例。接着,阐述了类的定义和组成,包括属性和行为,并展示了如何创建和使用对象。然后,讨论了成员变量与局部变量的区别,强调了封装的重要性,通过`private`关键字隐藏数据并提供`get/set`方法访问。最后,介绍了构造方法的定义和重载,以及标准类的制作规范,帮助初学者理解如何构建完整的Java类。
Java高级应用开发:AI赋能下的智能代码生成与优化
本文探讨了AI技术,特别是像DeepSeek这样的智能工具,在Java高级应用开发中的应用。AI在代码生成、优化、自动化测试等方面发挥重要作用,可自动生成高质量代码片段、提出优化建议并检测潜在错误,显著提升开发效率与代码质量。未来,AI将进一步推动Java开发的智能化和自动化,为开发者带来全新的开发体验。
Java高级应用开发:基于AI的微服务架构优化与性能调优
在现代企业级应用开发中,微服务架构虽带来灵活性和可扩展性,但也增加了系统复杂性和性能瓶颈。本文探讨如何利用AI技术,特别是像DeepSeek这样的智能工具,优化Java微服务架构。AI通过智能分析系统运行数据,自动识别并解决性能瓶颈,优化服务拆分、通信方式及资源管理,实现高效性能调优,助力开发者设计更合理的微服务架构,迎接未来智能化开发的新时代。
Java 高级面试技巧:yield() 与 sleep() 方法的使用场景和区别
本文详细解析了 Java 中 `Thread` 类的 `yield()` 和 `sleep()` 方法,解释了它们的作用、区别及为什么是静态方法。`yield()` 让当前线程释放 CPU 时间片,给其他同等优先级线程运行机会,但不保证暂停;`sleep()` 则让线程进入休眠状态,指定时间后继续执行。两者都是静态方法,因为它们影响线程调度机制而非单一线程行为。这些知识点在面试中常被提及,掌握它们有助于更好地应对多线程编程问题。
69 9
Java面试必问!run() 和 start() 方法到底有啥区别?
在多线程编程中,run和 start方法常常让开发者感到困惑。为什么调用 start 才能启动线程,而直接调用 run只是普通方法调用?这篇文章将通过一个简单的例子,详细解析这两者的区别,帮助你在面试中脱颖而出,理解多线程背后的机制和原理。
72 12
|
6天前
|
【Java并发】【线程池】带你从0-1入门线程池
欢迎来到我的技术博客!我是一名热爱编程的开发者,梦想是编写高端CRUD应用。2025年我正在沉淀中,博客更新速度加快,期待与你一起成长。 线程池是一种复用线程资源的机制,通过预先创建一定数量的线程并管理其生命周期,避免频繁创建/销毁线程带来的性能开销。它解决了线程创建成本高、资源耗尽风险、响应速度慢和任务执行缺乏管理等问题。
113 60
【Java并发】【线程池】带你从0-1入门线程池
|
2天前
|
【源码】【Java并发】【线程池】邀请您从0-1阅读ThreadPoolExecutor源码
当我们创建一个`ThreadPoolExecutor`的时候,你是否会好奇🤔,它到底发生了什么?比如:我传的拒绝策略、线程工厂是啥时候被使用的? 核心线程数是个啥?最大线程数和它又有什么关系?线程池,它是怎么调度,我们传入的线程?...不要着急,小手手点上关注、点赞、收藏。主播马上从源码的角度带你们探索神秘线程池的世界...
29 0
【源码】【Java并发】【线程池】邀请您从0-1阅读ThreadPoolExecutor源码

热门文章

最新文章