当前位置: 首页 > news >正文

每日一题之二分查找(一)

每日一题之二分查找(一)

1.题目(搜索插入位置)

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

请必须使用时间复杂度为 O(log n) 的算法。

示例 1:

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

示例 2:

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

示例 3:

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

提示:

  • 1 <= nums.length <= 104
  • -104 <= nums[i] <= 104
  • nums无重复元素升序 排列数组
  • -104 <= target <= 104

2.解题思路

因为数组是有序的排列数组,且无重复元素,所以可以使用二分来找下标

这里一共有四种情况

(1)数组中找到了目标元素,返回当前目标元素的下标结束

(2)目标元素不存在,应在数组的所有元素之前

(3)目标元素不存在,应在所有的元素之后

(4)目标元素不存在,应在数组中的某个位置

具体实现步骤

1.先找到这个数组的左边界,再找到这个数组的右边界,此时的范围就是整个数组

2.然后进行二分查找

(1)先找到中间位置的那个数,然后与目标值进行比较,

1> 如果当前的数比目标值小的话那么左边界变为中间位置向右一个的位置,继续进行查找

2> 如果当前的数比目标值小的话那么右边界变为中间位置向左一个的位置,继续进行查找

3> 如果当前的数和目标值相等的话,那么找到了

(2)当左边界比右边界大的时候,结束查找

3.那要添加元素的位置就是右边界+1的位置

3.代码

class Solution {
public:int searchInsert(vector<int>& nums, int target) {int left=0;int right=nums.size()-1;while(left<=right){//int mid=(left+right)>>1;这里通过学习发现可以进行优化//优化如下int mid=left+(right-left)/2;//优化后的代码if(nums[mid]==target){return mid;}if(nums[mid]>target){right=mid-1;}if(nums[mid]<target){left=mid+1;}}return right+1;}
};

相关文章:

每日一题之二分查找(一)

每日一题之二分查找&#xff08;一&#xff09; 1.题目&#xff08;搜索插入位置&#xff09; 给定一个排序数组和一个目标值&#xff0c;在数组中找到目标值&#xff0c;并返回其索引。如果目标值不存在于数组中&#xff0c;返回它将会被按顺序插入的位置。 请必须使用时间…...

Redisson的看门狗策略——保障Redis数据安全与稳定的机制

前言 自定义redis分布式锁无法自动续期&#xff0c;比如&#xff0c;一个锁设置了1分钟超时释放&#xff0c;如果拿到这个锁的线程在一分钟内没有执行完毕&#xff0c;那么这个锁就会被其他线程拿到&#xff0c;可能会导致严重的线上问题&#xff0c;在秒杀场景下&#xff0c;…...

2.2 消元法的概念

一、消元法介绍 消元法&#xff08;elimination&#xff09;是一个求解线性方程组的系统性方法。下面是使用消元法求解一个 2 2 2\times2 22 线性方程组的例子。消元之前&#xff0c;两个方程都有 x x x 和 y y y&#xff0c;消元后&#xff0c;第一个未知数 x x x 将从第…...

删除有序数组中的重复项

目录 题目&#xff1a; 示例&#xff1a; 题目分析&#xff1a; 解题思路&#xff1a; 题目&#xff1a; 给你一个 非严格递增排列 的数组 nums &#xff0c;请你 原地 删除重复出现的元素&#xff0c;使每个元素 只出现一次 &#xff0c;返回删除后数组的新长度。元素的…...

【数据库】

文章目录 1. 聚合函数练习&#xff1a; 2. 子查询 1. 聚合函数 where中过滤条件中不能写聚合函数&#xff0c;有聚合函数需要写到Having中 方式一效率高&#xff1a; Select执行流程 练习&#xff1a; 2. 第七题&#xff1a;count(*)有问题&#xff0c;原因是左外连接后…...

高级深入--day38

阳光热线问政平台 http://wz.sun0769.com/index.php/question/questionType?type4 爬取投诉帖子的编号、帖子的url、帖子的标题&#xff0c;和帖子里的内容。 items.py import scrapyclass DongguanItem(scrapy.Item):# 每个帖子的标题title scrapy.Field()# 每个帖子的编…...

基于springboot,vue校园社团管理系统

开发工具&#xff1a;IDEA 服务器&#xff1a;Tomcat9.0&#xff0c; jdk1.8 项目构建&#xff1a;maven 数据库&#xff1a;mysql5.7 系统分前后台&#xff0c;项目采用前后端分离 前端技术&#xff1a;vueelementUI 服务端技术&#xff1a;springbootmybatis-plus 本系…...

广州华锐互动:VR虚拟现实物理学习平台,开启数字化教学新格局

随着虚拟现实(VR)技术的不断发展&#xff0c;越来越多的领域开始应用这一技术。广州华锐互动开发的VR虚拟现实物理学习平台就得到了广泛应用&#xff0c;平台涉及力学、光学、热学等初中物理知识&#xff0c;还包含了物理名人、实验器具、物理现象的还原和学习&#xff0c;相比…...

【tio-websocket】8、T-IO对半包和粘包的处理

介绍 t-io对数据的解码是在DecodeRunnable中完成的,一个TCP连接对应一个DecodeRunnable半包粘包的处理也都在DecodeRunnable中完成的关于DecodeRunnable 先贴上 DecodeRunnable 的源代码: import java.nio.BufferUnderflowException; import java.nio.ByteBuffer; import j…...

【Linux】安装与配置虚拟机及虚拟机服务器坏境配置与连接

目录 操作系统介绍 什么是操作系统 常见操作系统 UNIX操作系统 linux操作系统 mac操作系统 嵌入式操作系统 个人版本和服务器版本的区别 安装VMWare虚拟机 VMWare虚拟网卡 ​编辑 配置虚拟网络编辑器 ​编辑 安装配置Windows Server 2012 R2 安装Windows Server 2…...

Redis常识

文章目录 缓存的三个风险数据结构淘汰策略 和 过期删除策略过期删除淘汰 如何理解单线程redis特性复制gossip协议事务&#xff08;和mysql不同&#xff0c;是不严格的事务 &#xff09;集群&#xff08;高可用&#xff09;管道持久化 缓存的三个风险 缓存雪崩&#xff08;缓存…...

Instant,LocalDate,LocalTime,LocalDateTime和ZonedDateTime

Instant 封装了从 1970-01-01T00:00:00Z 开始的秒数&#xff0c;相当于时间戳。 主要有两个属性&#xff1a; private final long seconds; private final int nanos;LocalDate 用于表示日期&#xff0c;包括年、月、日&#xff0c;例如 2017-12-03。 主要有三个属性&…...

Web入门笔记

Web入门笔记 HTTP协议 超文本传输协议 规定了浏览器和服务器之间数据传输的规则&#xff0c;请问数据和响应数据的格式 基于TCP请求-响应模式一次请求对应一次响应无状态的协议 请问数据格式 浏览器版本&#xff1a;解决浏览器兼容问题。GET请求体&#xff1a;存放请求参数…...

Linux网络编程二(TCP三次握手、四次挥手、TCP滑动窗口、MSS、TCP状态转换、多进程/多线程服务器实现)

TCP三次握手 TCP三次握手(TCP three-way handshake)是TCP协议建立可靠连接的过程&#xff0c;确保客户端和服务器之间可以进行可靠的通信。下面是TCP三次握手的详细过程&#xff1a; 假设客户端为A&#xff0c;服务器为B 1、第一次握手&#xff08;SYN1&#xff0c;seq500&…...

C#核心笔记——(一)C#和.NET Framework

C#是一种通用的&#xff0c;类型安全的面向对象编程语言。其目标是提高程序员生产力。 一.面向对象 C#实现了丰富的面向对象范式&#xff0c;包括封装、继承、多态。 C#面向对象特性包括&#xff1a; 统一的类型系统 类与接口 属性、方法、事件 C#支持纯函数模式 二、类型安…...

【2023年冬季】华为OD统一考试(B卷)题库清单(已收录345题),又快又全的 B 卷题库大整理

目录 专栏导读华为OD机试算法题太多了&#xff0c;知识点繁杂&#xff0c;如何刷题更有效率呢&#xff1f; 一、逻辑分析二、数据结构1、线性表① 数组② 双指针 2、map与list3、队列4、滑动窗口5、二叉树6、并查集7、栈 三、算法1、基础算法① 贪心算法② 二分查找③ 分治递归…...

云服务器的先驱,亚马逊云科技海外云服务器领军者

随着第三次工业革命的发展&#xff0c;移动互联网技术带来的信息技术革命为我们的生活带来了极大的便捷。其中&#xff0c;不少优秀的云服务器产品发挥了不可低估的作用&#xff0c;你或许听说过亚马逊云科技、谷歌GCP、IBM Cloud等优秀的海外云服务器。那么云服务器有哪些&…...

QT webengine显示HTML简单示例

文章目录 参考示例1TestWebenqine.promainwindow.hmainwindow.cppmain.cpp效果 示例2 (使用setDevToolsPage函数)main.cpp效果 参考 QT webengine显示HTML简单示例 示例1 编译器 : Desktop Qt 5.15.2 MSVC2019 64bit编辑器: QtCreator代码: TestWebenqine.pro # TestWeben…...

Spark_SQL函数定义(定义UDF函数、使用窗口函数)

一、UDF函数定义 &#xff08;1&#xff09;函数定义 &#xff08;2&#xff09;Spark支持定义函数 &#xff08;3&#xff09;定义UDF函数 &#xff08;4&#xff09;定义返回Array类型的UDF &#xff08;5&#xff09;定义返回字典类型的UDF 二、窗口函数 &#xff08;1&…...

【Leetcode】【每日一题】【中等】274. H 指数

力扣&#xff08;LeetCode&#xff09;官网 - 全球极客挚爱的技术成长平台备战技术面试&#xff1f;力扣提供海量技术面试资源&#xff0c;帮助你高效提升编程技能&#xff0c;轻松拿下世界 IT 名企 Dream Offer。https://leetcode.cn/problems/h-index/description/?envTyped…...

XML Group端口详解

在XML数据映射过程中&#xff0c;经常需要对数据进行分组聚合操作。例如&#xff0c;当处理包含多个物料明细的XML文件时&#xff0c;可能需要将相同物料号的明细归为一组&#xff0c;或对相同物料号的数量进行求和计算。传统实现方式通常需要编写脚本代码&#xff0c;增加了开…...

练习(含atoi的模拟实现,自定义类型等练习)

一、结构体大小的计算及位段 &#xff08;结构体大小计算及位段 详解请看&#xff1a;自定义类型&#xff1a;结构体进阶-CSDN博客&#xff09; 1.在32位系统环境&#xff0c;编译选项为4字节对齐&#xff0c;那么sizeof(A)和sizeof(B)是多少&#xff1f; #pragma pack(4)st…...

【ROS】Nav2源码之nav2_behavior_tree-行为树节点列表

1、行为树节点分类 在 Nav2(Navigation2)的行为树框架中,行为树节点插件按照功能分为 Action(动作节点)、Condition(条件节点)、Control(控制节点) 和 Decorator(装饰节点) 四类。 1.1 动作节点 Action 执行具体的机器人操作或任务,直接与硬件、传感器或外部系统…...

《通信之道——从微积分到 5G》读书总结

第1章 绪 论 1.1 这是一本什么样的书 通信技术&#xff0c;说到底就是数学。 那些最基础、最本质的部分。 1.2 什么是通信 通信 发送方 接收方 承载信息的信号 解调出其中承载的信息 信息在发送方那里被加工成信号&#xff08;调制&#xff09; 把信息从信号中抽取出来&am…...

DIY|Mac 搭建 ESP-IDF 开发环境及编译小智 AI

前一阵子在百度 AI 开发者大会上&#xff0c;看到基于小智 AI DIY 玩具的演示&#xff0c;感觉有点意思&#xff0c;想着自己也来试试。 如果只是想烧录现成的固件&#xff0c;乐鑫官方除了提供了 Windows 版本的 Flash 下载工具 之外&#xff0c;还提供了基于网页版的 ESP LA…...

PL0语法,分析器实现!

简介 PL/0 是一种简单的编程语言,通常用于教学编译原理。它的语法结构清晰,功能包括常量定义、变量声明、过程(子程序)定义以及基本的控制结构(如条件语句和循环语句)。 PL/0 语法规范 PL/0 是一种教学用的小型编程语言,由 Niklaus Wirth 设计,用于展示编译原理的核…...

MySQL 8.0 OCP 英文题库解析(十三)

Oracle 为庆祝 MySQL 30 周年&#xff0c;截止到 2025.07.31 之前。所有人均可以免费考取原价245美元的MySQL OCP 认证。 从今天开始&#xff0c;将英文题库免费公布出来&#xff0c;并进行解析&#xff0c;帮助大家在一个月之内轻松通过OCP认证。 本期公布试题111~120 试题1…...

tree 树组件大数据卡顿问题优化

问题背景 项目中有用到树组件用来做文件目录&#xff0c;但是由于这个树组件的节点越来越多&#xff0c;导致页面在滚动这个树组件的时候浏览器就很容易卡死。这种问题基本上都是因为dom节点太多&#xff0c;导致的浏览器卡顿&#xff0c;这里很明显就需要用到虚拟列表的技术&…...

Spring Cloud Gateway 中自定义验证码接口返回 404 的排查与解决

Spring Cloud Gateway 中自定义验证码接口返回 404 的排查与解决 问题背景 在一个基于 Spring Cloud Gateway WebFlux 构建的微服务项目中&#xff0c;新增了一个本地验证码接口 /code&#xff0c;使用函数式路由&#xff08;RouterFunction&#xff09;和 Hutool 的 Circle…...

云原生安全实战:API网关Kong的鉴权与限流详解

&#x1f525;「炎码工坊」技术弹药已装填&#xff01; 点击关注 → 解锁工业级干货【工具实测|项目避坑|源码燃烧指南】 一、基础概念 1. API网关&#xff08;API Gateway&#xff09; API网关是微服务架构中的核心组件&#xff0c;负责统一管理所有API的流量入口。它像一座…...