当前位置: 首页 > 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…...

基于Flask实现的医疗保险欺诈识别监测模型

基于Flask实现的医疗保险欺诈识别监测模型 项目截图 项目简介 社会医疗保险是国家通过立法形式强制实施&#xff0c;由雇主和个人按一定比例缴纳保险费&#xff0c;建立社会医疗保险基金&#xff0c;支付雇员医疗费用的一种医疗保险制度&#xff0c; 它是促进社会文明和进步的…...

第一篇:Agent2Agent (A2A) 协议——协作式人工智能的黎明

AI 领域的快速发展正在催生一个新时代&#xff0c;智能代理&#xff08;agents&#xff09;不再是孤立的个体&#xff0c;而是能够像一个数字团队一样协作。然而&#xff0c;当前 AI 生态系统的碎片化阻碍了这一愿景的实现&#xff0c;导致了“AI 巴别塔问题”——不同代理之间…...

土地利用/土地覆盖遥感解译与基于CLUE模型未来变化情景预测;从基础到高级,涵盖ArcGIS数据处理、ENVI遥感解译与CLUE模型情景模拟等

&#x1f50d; 土地利用/土地覆盖数据是生态、环境和气象等诸多领域模型的关键输入参数。通过遥感影像解译技术&#xff0c;可以精准获取历史或当前任何一个区域的土地利用/土地覆盖情况。这些数据不仅能够用于评估区域生态环境的变化趋势&#xff0c;还能有效评价重大生态工程…...

使用Spring AI和MCP协议构建图片搜索服务

目录 使用Spring AI和MCP协议构建图片搜索服务 引言 技术栈概览 项目架构设计 架构图 服务端开发 1. 创建Spring Boot项目 2. 实现图片搜索工具 3. 配置传输模式 Stdio模式&#xff08;本地调用&#xff09; SSE模式&#xff08;远程调用&#xff09; 4. 注册工具提…...

莫兰迪高级灰总结计划简约商务通用PPT模版

莫兰迪高级灰总结计划简约商务通用PPT模版&#xff0c;莫兰迪调色板清新简约工作汇报PPT模版&#xff0c;莫兰迪时尚风极简设计PPT模版&#xff0c;大学生毕业论文答辩PPT模版&#xff0c;莫兰迪配色总结计划简约商务通用PPT模版&#xff0c;莫兰迪商务汇报PPT模版&#xff0c;…...

【JavaSE】多线程基础学习笔记

多线程基础 -线程相关概念 程序&#xff08;Program&#xff09; 是为完成特定任务、用某种语言编写的一组指令的集合简单的说:就是我们写的代码 进程 进程是指运行中的程序&#xff0c;比如我们使用QQ&#xff0c;就启动了一个进程&#xff0c;操作系统就会为该进程分配内存…...

计算机基础知识解析:从应用到架构的全面拆解

目录 前言 1、 计算机的应用领域&#xff1a;无处不在的数字助手 2、 计算机的进化史&#xff1a;从算盘到量子计算 3、计算机的分类&#xff1a;不止 “台式机和笔记本” 4、计算机的组件&#xff1a;硬件与软件的协同 4.1 硬件&#xff1a;五大核心部件 4.2 软件&#…...

自然语言处理——文本分类

文本分类 传统机器学习方法文本表示向量空间模型 特征选择文档频率互信息信息增益&#xff08;IG&#xff09; 分类器设计贝叶斯理论&#xff1a;线性判别函数 文本分类性能评估P-R曲线ROC曲线 将文本文档或句子分类为预定义的类或类别&#xff0c; 有单标签多类别文本分类和多…...

Appium下载安装配置保姆教程(图文详解)

目录 一、Appium软件介绍 1.特点 2.工作原理 3.应用场景 二、环境准备 安装 Node.js 安装 Appium 安装 JDK 安装 Android SDK 安装Python及依赖包 三、安装教程 1.Node.js安装 1.1.下载Node 1.2.安装程序 1.3.配置npm仓储和缓存 1.4. 配置环境 1.5.测试Node.j…...

【技巧】dify前端源代码修改第一弹-增加tab页

回到目录 【技巧】dify前端源代码修改第一弹-增加tab页 尝试修改dify的前端源代码&#xff0c;在知识库增加一个tab页"HELLO WORLD"&#xff0c;完成后的效果如下 [gif01] 1. 前端代码进入调试模式 参考 【部署】win10的wsl环境下启动dify的web前端服务 启动调试…...