力扣35搜索插入位置:思路分析+图文详解+代码实现+拓展java源码

简介: 力扣35搜索插入位置:思路分析+图文详解+代码实现+拓展java源码

第一部分:题目描述

🏠 链接:35. 搜索插入位置 - 力扣(LeetCode)

⭐ 难度:简单

第二部分:思路分析

我们可以先看下普通二分查找的代码:满足了查到返回索引,查不到返回-1

public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        int mid;
        while (left <= right) {
            // 得到中间索引
            /*
                考虑到 left+right 的值可能会超过 int可表示 的最大值,我们不再对他们的和直接除以2
                我们知道 除以2 的操作可以用 位运算 >>1 来代替
                但还不够,由于 (left+right) 值溢出表示负数,>>1 只是做 除以2 操作,最高位符号位不变,依旧为1表示负数,负数除以2依旧是负数
                这时候我们可以修改为 无符号右移 >>>1 ,低位溢出,高位补0,那么最高位符号位为0就表示正数了
             */
            mid = (left + right) >>> 1;
            if (target < nums[mid]) {
                // 如果目标值小于中间值
                right = mid - 1;
            } else if (nums[mid] < target) {
                // 如果目标值大于中间值
                left = mid + 1;
            } else {
                return mid;
            }
        }
        return -1;
    }

而这道题目的要求是:查到返回索引,查不到返回应该插入位置的索引。

我们可以这样来分析:

  1. 如果能够查询得到,还是走原来的逻辑,即 else 块中的 return mid
  2. 如果查询不到,你首先必须肯定这样一件事:
  • 全部搜索完还查找不到时 while 循环会退出
  • 具体是为什么会退出呢?==》left <= right 的条件不成立,即 left > right,更具体的说是 right + 1 == left 了。

  1. 紧接着,我们又必须赞成一件事:
  • 在 left > right ,即 right + 1 == left 之前的while循环中,肯定有 left == right 成立

  • 在以 left == right 为循环条件的循环体中,进行了 if 语句的right指针向左移动 或者 else-if 语句的left指针向右移动,而导致出现了 right + 1 == left ,自此循环退出。
  1. 那么这个时候就很好分析了,我们知道了最后一次循环时的循环条件是left == right,至于是if 语句的right指针向左移动还是else-if 语句的left指针向右移动都有可能,我们分这两种情况进行分析:
  • if 语句的right指针向左移动

    当目标值小于 中间索引mid对应值 时,会走 if 语句导致 right 指针左移,自此 while 循环会结束。

    对于是一个从小到大排序的升序数组,我们知道插入位置应该放在 中间索引mid 的前面,即插入位置应当就是 当前中间索引mid ,那不就是 left指针 的位置吗?
  • else-if 语句的left指针向右移动

    当目标值大于 中间索引mid对应值 时,会走 else-if 语句导致 left 指针右移,自此 while 循环会结束。

    对于是一个从小到大排序的升序数组,我们知道插入位置应该放在 中间索引mid 的后面,而最后一次循环操作后 left 指针从原来的 mid 位置右移了一位,那插入位置不就是最终 left指针 的位置吗?
  1. 因此,综上所述
  • 查找到了,就是原二分查找的 return mid
  • 未查找到,就是最终 left指针 的位置。 因此只需要将 return -1 改为 return left 即可。

第三部分:代码实现

public int searchInsert(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        int mid;
        while (left <= right) {
            // 得到中间索引
            /*
                考虑到 left+right 的值可能会超过 int可表示 的最大值,我们不再对他们的和直接除以2
                我们知道 除以2 的操作可以用 位运算 >>1 来代替
                但还不够,由于 (left+right) 值溢出表示负数,>>1 只是做 除以2 操作,最高位符号位不变,依旧为1表示负数,负数除以2依旧是负数
                这时候我们可以修改为 无符号右移 >>>1 ,低位溢出,高位补0,那么最高位符号位为0就表示正数了
             */
            mid = (left + right) >>> 1;
            if (target < nums[mid]) {
                // 如果目标值小于中间值
                right = mid - 1;
            } else if (nums[mid] < target) {
                // 如果目标值大于中间值
                left = mid + 1;
            } else {
                return mid;
            }
        }
        return left;
    }

第四部分:拓展-Java底层源码对二分查找的实现

⭐ 在 Arrays 类中的方法 binarySearch0(int[] a, int fromIndex, int toIndex, int key),源码如下:

/**
     * 使用二进制搜索算法在指定的整数数组中搜索指定的值。在进行此调用之前,必须对数组进行排序(按方法排序 sort(int[]) )。
     * 如果未排序,则结果未定义。如果数组包含多个具有指定值的元素,则无法保证会找到哪个元素。
     * 参数:
   *    a – 要搜索的数组 
   *    key – 要搜索的值
   * 返回:搜索键的索引(如果它包含在数组中);否则,( -(插入点)-1)。
   * 插入点定义为将键插入数组的 点 :第一个元素的索引大于键,如果数组中的所有元素都小于指定的键,则为 a.length 。
   * 请注意,这保证了当且仅当找到键时返回值将为 >= 0。
     */
    public static int binarySearch(int[] a, int key) {
        return binarySearch0(a, 0, a.length, key);
    }
    // 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.
    }

第五部分:拓展-利用Arrays实现二分查找目标值,不存在则插入

public static void main(String[] args) {
        // 二分查找目标值,不存在则插入
        /*
            原始数组:[2,5,8]
            查找目标值:4
            查询不到,返回的结果为 r = -待插入点索引-1
            在这里带插入点索引为 1,对应 r = -2
            那么我们分成这几步来进行拷贝:
                - 1.新建数组,大小为原数组的大小+1:         [0,0,0,0]
                - 2.将待插入点索引之前的数据放入新数组:     [2,0,0,0]
                - 3.将目标值放入到待插入点索引的位置:       [2,4,0,0]
                - 4.将原数组后面的数据都相继拷贝到新数组后面: [2,4,5,8]
         */
        // 定义原数组与目标值
        int[] oldArray = {2, 5, 8};
        int target = 4;
        // 搜索目标值4,没有找到,返回结果为 r =  -待插入点索引-1,这里的 r=-2
        int r = Arrays.binarySearch(oldArray, target);
        // r < 0 说明没有找到目标值,就插入
        if (r < 0) {
            // 获取待插入索引
            int insertIndex = -r - 1;
            // 1.新建数组,大小为原数组的大小+1
            int[] newArray = new int[oldArray.length + 1];
            // 2.将待插入点索引之前的数据放入新数组
            System.arraycopy(oldArray, 0, newArray, 0, insertIndex);
            // 3.将目标值放入到待插入点索引的位置
            newArray[insertIndex] = target;
            // 4.将原数组后面的数据都相继拷贝到新数组后面
            System.arraycopy(oldArray, insertIndex, newArray, insertIndex + 1, oldArray.length - insertIndex);
            System.out.println(Arrays.toString(newArray));
        }
    }

第六部分:拓展-(left + right) >>> 1的分析

在本文中我使用的是 (left + right) >>> 1 来代替 (left + right) / 2,目的是解决 left + right 超过int最大值 的问题。

我们先来举个模拟问题的发生:

public static void main(String[] args) {
        // 模拟 二分查找中的 left
        int left = 100;
        // 模拟 二分查找中的 right
        int right = Integer.MAX_VALUE - 1;
        // 此时 left+right 的值超过了 int范围 的最大值,导致 left + right 的结果为负数
        // 然后对负数进行除以2操作,结果依旧为负数
        int mid = (left + right) / 2;
        // 输出结果为 -1073741775
        System.out.println(mid);
    }

那如何解决这个问题呢?我们可以使用 位运算 来代替 /2 的操作。

  • 算数右移 >> :低位溢出,符号位不变,并用符号位补溢出的高位。
  • 逻辑右击(无符号右移)>>>:低位溢出,高位补0。

由于最高位符号位为0表示该数为正数,因此相比于 >> 做到了能将一个 负数 无符号右移后变成 正数。

第七部分:方法-返回≥目标的最靠左索引

除了使用第三部分的代码实现方法,还可以使用 Leftmost 方式解决该问题:

具体解释参考:力扣704二分查找:思路分析+代码实现(递归与非递归)_是谢添啊的博客-CSDN博客

public int searchInsert(int[] array, int target) {
        int left = 0;
        int right = array.length - 1;
        int mid;
        while (left <= right) {
            mid = (left + right) >>> 1;
            if (target <= array[mid]) {
                // array[mid] 满足大于等于目标值,因此可以记录
                right = mid - 1;
            } else if (array[mid] < target) {
                // 目标值大于中间索引值,缩小左范围
                left = mid + 1;
            }
        }
        // 返回结果
        return left;
    }


相关文章
|
3天前
|
监控 Java 应用服务中间件
高级java面试---spring.factories文件的解析源码API机制
【11月更文挑战第20天】Spring Boot是一个用于快速构建基于Spring框架的应用程序的开源框架。它通过自动配置、起步依赖和内嵌服务器等特性,极大地简化了Spring应用的开发和部署过程。本文将深入探讨Spring Boot的背景历史、业务场景、功能点以及底层原理,并通过Java代码手写模拟Spring Boot的启动过程,特别是spring.factories文件的解析源码API机制。
15 2
|
1月前
|
Java Apache Maven
Java百项管理之新闻管理系统 熟悉java语法——大学生作业 有源码!!!可运行!!!
文章提供了使用Apache POI库在Java中创建和读取Excel文件的详细代码示例,包括写入数据到Excel和从Excel读取数据的方法。
59 6
Java百项管理之新闻管理系统 熟悉java语法——大学生作业 有源码!!!可运行!!!
|
7天前
|
人工智能 监控 数据可视化
Java智慧工地信息管理平台源码 智慧工地信息化解决方案SaaS源码 支持二次开发
智慧工地系统是依托物联网、互联网、AI、可视化建立的大数据管理平台,是一种全新的管理模式,能够实现劳务管理、安全施工、绿色施工的智能化和互联网化。围绕施工现场管理的人、机、料、法、环五大维度,以及施工过程管理的进度、质量、安全三大体系为基础应用,实现全面高效的工程管理需求,满足工地多角色、多视角的有效监管,实现工程建设管理的降本增效,为监管平台提供数据支撑。
24 3
|
12天前
|
运维 自然语言处理 供应链
Java云HIS医院管理系统源码 病案管理、医保业务、门诊、住院、电子病历编辑器
通过门诊的申请,或者直接住院登记,通过”护士工作站“分配患者,完成后,进入医生患者列表,医生对应开具”长期医嘱“和”临时医嘱“,并在电子病历中,记录病情。病人出院时,停止长期医嘱,开具出院医嘱。进入出院审核,审核医嘱与住院通过后,病人结清缴费,完成出院。
42 3
|
18天前
|
JavaScript Java 项目管理
Java毕设学习 基于SpringBoot + Vue 的医院管理系统 持续给大家寻找Java毕设学习项目(附源码)
基于SpringBoot + Vue的医院管理系统,涵盖医院、患者、挂号、药物、检查、病床、排班管理和数据分析等功能。开发工具为IDEA和HBuilder X,环境需配置jdk8、Node.js14、MySQL8。文末提供源码下载链接。
|
21天前
|
移动开发 前端开发 JavaScript
java家政系统成品源码的关键特点和技术应用
家政系统成品源码是已开发完成的家政服务管理软件,支持用户注册、登录、管理个人资料,家政人员信息管理,服务项目分类,订单与预约管理,支付集成,评价与反馈,地图定位等功能。适用于各种规模的家政服务公司,采用uniapp、SpringBoot、MySQL等技术栈,确保高效管理和优质用户体验。
|
1月前
|
JSON 前端开发 Java
震惊!图文并茂——Java后端如何响应不同格式的数据给前端(带源码)
文章介绍了Java后端如何使用Spring Boot框架响应不同格式的数据给前端,包括返回静态页面、数据、HTML代码片段、JSON对象、设置状态码和响应的Header。
132 1
震惊!图文并茂——Java后端如何响应不同格式的数据给前端(带源码)
|
1月前
|
算法 索引
LeetCode(搜索插入位置)
如何使用二分查找算法来解决LeetCode上的“搜索插入位置”问题,确保时间复杂度为O(log n),并提供了详细的代码实现和分析。
14 2
|
1月前
|
索引
Leetcode第三十三题(搜索旋转排序数组)
这篇文章介绍了解决LeetCode第33题“搜索旋转排序数组”的方法,该问题要求在旋转过的升序数组中找到给定目标值的索引,如果存在则返回索引,否则返回-1,文章提供了一个时间复杂度为O(logn)的二分搜索算法实现。
18 0
Leetcode第三十三题(搜索旋转排序数组)
|
1月前
|
存储 前端开发 Java
Java后端如何进行文件上传和下载 —— 本地版(文末配绝对能用的源码,超详细,超好用,一看就懂,博主在线解答) 文件如何预览和下载?(超简单教程)
本文详细介绍了在Java后端进行文件上传和下载的实现方法,包括文件上传保存到本地的完整流程、文件下载的代码实现,以及如何处理文件预览、下载大小限制和运行失败的问题,并提供了完整的代码示例。
438 1