千家信息网

请输入关键字词

热门搜索排行

最新搜索排行

导航： 首页 > 互联网科技 >

如何使用java实现搜索插入位置

发表于：2025-01-23 作者：千家信息网编辑
千家信息网最后更新 2025年01月23日，这篇文章主要介绍了如何使用java实现搜索插入位置，具有一定借鉴价值，感兴趣的朋友可以参考下，希望大家阅读完这篇文章之后大有收获，下面让小编带着大家一起了解一下。题目描述给定一个排序数组和一个目标值，
千家信息网最后更新 2025年01月23日如何使用java实现搜索插入位置

这篇文章主要介绍了如何使用java实现搜索插入位置，具有一定借鉴价值，感兴趣的朋友可以参考下，希望大家阅读完这篇文章之后大有收获，下面让小编带着大家一起了解一下。


题目描述

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

你可以假设数组中无重复元素。

示例 1:

输入: [1,3,5,6], 5输出: 2

示例 2:

输入: [1,3,5,6], 2输出: 1

示例 3:

输入: [1,3,5,6], 7输出: 4

示例 4:

输入: [1,3,5,6], 0输出: 0

解题方案

思路

  • 标签：二分查找

  • 如果该题目暴力解决的话需要O(n)的时间复杂度，但是如果二分的话则可以降低到O(logn)的时间复杂度

  • 整体思路和普通的二分查找几乎没有区别，先设定左侧下标left和右侧下标right，再计算中间下标mid

  • 每次根据nums[mid]和target之间的大小进行判断，相等则直接返回下标，nums[mid]则left右移，nums[mid]>target则right左移

  • 查找结束如果没有相等值则返回left，该值为插入位置

  • 时间复杂度：O(logn)

二分查找的思路不难理解，但是边界条件容易出错，比如循环结束条件中left和right的关系，更新left和right位置时要不要加1减1。

下面给出两个可以直接套用的模板，记住就好了，免除边界条件出错。

class Solution {    public int searchInsert(int[] nums, int target) {        int left = 0, right = nums.length - 1; // 注意        while(left <= right) { // 注意            int mid = (left + right) / 2; // 注意            if(nums[mid] == target) { // 注意                // 相关逻辑            } else if(nums[mid] < target) {                left = mid + 1; // 注意            } else {                right = mid - 1; // 注意            }        }        // 相关返回值        return 0;    }}

或

class Solution {    public int searchInsert(int[] nums, int target) {        int left = 0, right = nums.length; // 注意        while(left < right) { // 注意            int mid = (left + right) / 2; // 注意            if(nums[mid] == target) {                // 相关逻辑            } else if(nums[mid] < target) {                left = mid + 1; // 注意            } else {                right = mid; // 注意            }        }        // 相关返回值        return 0;    }}

代码

class Solution {    public int searchInsert(int[] nums, int target) {        int left = 0, right = nums.length - 1;        while(left <= right) {            int mid = (left + right) / 2;            if(nums[mid] == target) {                return mid;            } else if(nums[mid] < target) {                left = mid + 1;            } else {                right = mid - 1;            }        }        return left;    }}

画解

感谢你能够认真阅读完这篇文章，希望小编分享的"如何使用java实现搜索插入位置"这篇文章对大家有帮助，同时也希望大家多多支持，关注行业资讯频道，更多相关知识等着你来学习!

很赞哦！
位置 下标 数组 示例 篇文章 输入 输出 复杂 复杂度 思路 时间 条件 目标 目标值 搜索 边界 逻辑 题目 普通 两个 数据库的安全要保护哪些东西 数据库安全各自的含义是什么 生产安全数据库录入 数据库的安全性及管理 数据库安全策略包含哪些 海淀数据库安全审计系统 建立农村房屋安全信息数据库 易用的数据库客户端支持安全管理 连接数据库失败ssl安全错误 数据库的锁怎样保障安全 符萍服务器 瀑布模型的软件开发模式 打印机打印服务器错误 如何在服务器上面建造软件 必联网络技术有限公司 美国服务器吧 服务器关闭了怎么进游戏 怎样关闭代理服务器 dhcp服务器管理器 资阳市网络安全平台 常考网络技术题库 ajax加载下拉框数据库 云服务器备份方案 南宁软件开发区域 脚本怎么创建数据库表 抖音网络安全中心 普陀区质量软件开发咨询热线 线美互联网科技 招聘信息 虚拟机登录王者服务器没反应 关于网络安全的杂志 软件开发怎么赔钱 数据库表设计项目实例 数据库安全警告怎么关闭 方舟生存进化服务器炸服两天 玉林网络安全支队支队长 数据库表名正则表达式 车载网络技术试卷答案 金仓数据库安装手册 普陀区质量软件开发咨询热线 微信多开一键转发软件开发

相关文章

0