每日一题之二分查找(一)
每日一题之二分查找(一)
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] <= 104nums为 无重复元素 的 升序 排列数组-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;}
};
相关文章:
每日一题之二分查找(一)
每日一题之二分查找(一) 1.题目(搜索插入位置) 给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。 请必须使用时间…...
Redisson的看门狗策略——保障Redis数据安全与稳定的机制
前言 自定义redis分布式锁无法自动续期,比如,一个锁设置了1分钟超时释放,如果拿到这个锁的线程在一分钟内没有执行完毕,那么这个锁就会被其他线程拿到,可能会导致严重的线上问题,在秒杀场景下,…...
2.2 消元法的概念
一、消元法介绍 消元法(elimination)是一个求解线性方程组的系统性方法。下面是使用消元法求解一个 2 2 2\times2 22 线性方程组的例子。消元之前,两个方程都有 x x x 和 y y y,消元后,第一个未知数 x x x 将从第…...
删除有序数组中的重复项
目录 题目: 示例: 题目分析: 解题思路: 题目: 给你一个 非严格递增排列 的数组 nums ,请你 原地 删除重复出现的元素,使每个元素 只出现一次 ,返回删除后数组的新长度。元素的…...
【数据库】
文章目录 1. 聚合函数练习: 2. 子查询 1. 聚合函数 where中过滤条件中不能写聚合函数,有聚合函数需要写到Having中 方式一效率高: Select执行流程 练习: 2. 第七题:count(*)有问题,原因是左外连接后…...
高级深入--day38
阳光热线问政平台 http://wz.sun0769.com/index.php/question/questionType?type4 爬取投诉帖子的编号、帖子的url、帖子的标题,和帖子里的内容。 items.py import scrapyclass DongguanItem(scrapy.Item):# 每个帖子的标题title scrapy.Field()# 每个帖子的编…...
基于springboot,vue校园社团管理系统
开发工具:IDEA 服务器:Tomcat9.0, jdk1.8 项目构建:maven 数据库:mysql5.7 系统分前后台,项目采用前后端分离 前端技术:vueelementUI 服务端技术:springbootmybatis-plus 本系…...
广州华锐互动:VR虚拟现实物理学习平台,开启数字化教学新格局
随着虚拟现实(VR)技术的不断发展,越来越多的领域开始应用这一技术。广州华锐互动开发的VR虚拟现实物理学习平台就得到了广泛应用,平台涉及力学、光学、热学等初中物理知识,还包含了物理名人、实验器具、物理现象的还原和学习,相比…...
【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协议事务(和mysql不同,是不严格的事务 )集群(高可用)管道持久化 缓存的三个风险 缓存雪崩(缓存…...
Instant,LocalDate,LocalTime,LocalDateTime和ZonedDateTime
Instant 封装了从 1970-01-01T00:00:00Z 开始的秒数,相当于时间戳。 主要有两个属性: private final long seconds; private final int nanos;LocalDate 用于表示日期,包括年、月、日,例如 2017-12-03。 主要有三个属性&…...
Web入门笔记
Web入门笔记 HTTP协议 超文本传输协议 规定了浏览器和服务器之间数据传输的规则,请问数据和响应数据的格式 基于TCP请求-响应模式一次请求对应一次响应无状态的协议 请问数据格式 浏览器版本:解决浏览器兼容问题。GET请求体:存放请求参数…...
Linux网络编程二(TCP三次握手、四次挥手、TCP滑动窗口、MSS、TCP状态转换、多进程/多线程服务器实现)
TCP三次握手 TCP三次握手(TCP three-way handshake)是TCP协议建立可靠连接的过程,确保客户端和服务器之间可以进行可靠的通信。下面是TCP三次握手的详细过程: 假设客户端为A,服务器为B 1、第一次握手(SYN1,seq500&…...
C#核心笔记——(一)C#和.NET Framework
C#是一种通用的,类型安全的面向对象编程语言。其目标是提高程序员生产力。 一.面向对象 C#实现了丰富的面向对象范式,包括封装、继承、多态。 C#面向对象特性包括: 统一的类型系统 类与接口 属性、方法、事件 C#支持纯函数模式 二、类型安…...
【2023年冬季】华为OD统一考试(B卷)题库清单(已收录345题),又快又全的 B 卷题库大整理
目录 专栏导读华为OD机试算法题太多了,知识点繁杂,如何刷题更有效率呢? 一、逻辑分析二、数据结构1、线性表① 数组② 双指针 2、map与list3、队列4、滑动窗口5、二叉树6、并查集7、栈 三、算法1、基础算法① 贪心算法② 二分查找③ 分治递归…...
云服务器的先驱,亚马逊云科技海外云服务器领军者
随着第三次工业革命的发展,移动互联网技术带来的信息技术革命为我们的生活带来了极大的便捷。其中,不少优秀的云服务器产品发挥了不可低估的作用,你或许听说过亚马逊云科技、谷歌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函数定义 (1)函数定义 (2)Spark支持定义函数 (3)定义UDF函数 (4)定义返回Array类型的UDF (5)定义返回字典类型的UDF 二、窗口函数 (1&…...
【Leetcode】【每日一题】【中等】274. H 指数
力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台备战技术面试?力扣提供海量技术面试资源,帮助你高效提升编程技能,轻松拿下世界 IT 名企 Dream Offer。https://leetcode.cn/problems/h-index/description/?envTyped…...
UE5 学习系列(三)创建和移动物体
这篇博客是该系列的第三篇,是在之前两篇博客的基础上展开,主要介绍如何在操作界面中创建和拖动物体,这篇博客跟随的视频链接如下: B 站视频:s03-创建和移动物体 如果你不打算开之前的博客并且对UE5 比较熟的话按照以…...
Golang dig框架与GraphQL的完美结合
将 Go 的 Dig 依赖注入框架与 GraphQL 结合使用,可以显著提升应用程序的可维护性、可测试性以及灵活性。 Dig 是一个强大的依赖注入容器,能够帮助开发者更好地管理复杂的依赖关系,而 GraphQL 则是一种用于 API 的查询语言,能够提…...
css的定位(position)详解:相对定位 绝对定位 固定定位
在 CSS 中,元素的定位通过 position 属性控制,共有 5 种定位模式:static(静态定位)、relative(相对定位)、absolute(绝对定位)、fixed(固定定位)和…...
Java 二维码
Java 二维码 **技术:**谷歌 ZXing 实现 首先添加依赖 <!-- 二维码依赖 --><dependency><groupId>com.google.zxing</groupId><artifactId>core</artifactId><version>3.5.1</version></dependency><de…...
[ACTF2020 新生赛]Include 1(php://filter伪协议)
题目 做法 启动靶机,点进去 点进去 查看URL,有 ?fileflag.php说明存在文件包含,原理是php://filter 协议 当它与包含函数结合时,php://filter流会被当作php文件执行。 用php://filter加编码,能让PHP把文件内容…...
Java 与 MySQL 性能优化:MySQL 慢 SQL 诊断与分析方法详解
文章目录 一、开启慢查询日志,定位耗时SQL1.1 查看慢查询日志是否开启1.2 临时开启慢查询日志1.3 永久开启慢查询日志1.4 分析慢查询日志 二、使用EXPLAIN分析SQL执行计划2.1 EXPLAIN的基本使用2.2 EXPLAIN分析案例2.3 根据EXPLAIN结果优化SQL 三、使用SHOW PROFILE…...
[拓扑优化] 1.概述
常见的拓扑优化方法有:均匀化法、变密度法、渐进结构优化法、水平集法、移动可变形组件法等。 常见的数值计算方法有:有限元法、有限差分法、边界元法、离散元法、无网格法、扩展有限元法、等几何分析等。 将上述数值计算方法与拓扑优化方法结合&#…...
小智AI+MCP
什么是小智AI和MCP 如果还不清楚的先看往期文章 手搓小智AI聊天机器人 MCP 深度解析:AI 的USB接口 如何使用小智MCP 1.刷支持mcp的小智固件 2.下载官方MCP的示例代码 Github:https://github.com/78/mcp-calculator 安这个步骤执行 其中MCP_ENDPOI…...
HTML中各种标签的作用
一、HTML文件主要标签结构及说明 1. <!DOCTYPE html> 作用:声明文档类型,告知浏览器这是 HTML5 文档。 必须:是。 2. <html lang“zh”>. </html> 作用:包裹整个网页内容,lang"z…...
STL 2迭代器
文章目录 1.迭代器2.输入迭代器3.输出迭代器1.插入迭代器 4.前向迭代器5.双向迭代器6.随机访问迭代器7.不同容器返回的迭代器类型1.输入 / 输出迭代器2.前向迭代器3.双向迭代器4.随机访问迭代器5.特殊迭代器适配器6.为什么 unordered_set 只提供前向迭代器? 1.迭代器…...
