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

JavaScript 中的 ES|QL:利用 Apache Arrow 工具

作者&#xff1a;来自 Elastic Jeffrey Rengifo 学习如何将 ES|QL 与 JavaScript 的 Apache Arrow 客户端工具一起使用。 想获得 Elastic 认证吗&#xff1f;了解下一期 Elasticsearch Engineer 培训的时间吧&#xff01; Elasticsearch 拥有众多新功能&#xff0c;助你为自己…...

【位运算】消失的两个数字(hard)

消失的两个数字&#xff08;hard&#xff09; 题⽬描述&#xff1a;解法&#xff08;位运算&#xff09;&#xff1a;Java 算法代码&#xff1a;更简便代码 题⽬链接&#xff1a;⾯试题 17.19. 消失的两个数字 题⽬描述&#xff1a; 给定⼀个数组&#xff0c;包含从 1 到 N 所有…...

UDP(Echoserver)

网络命令 Ping 命令 检测网络是否连通 使用方法: ping -c 次数 网址ping -c 3 www.baidu.comnetstat 命令 netstat 是一个用来查看网络状态的重要工具. 语法&#xff1a;netstat [选项] 功能&#xff1a;查看网络状态 常用选项&#xff1a; n 拒绝显示别名&#…...

React Native在HarmonyOS 5.0阅读类应用开发中的实践

一、技术选型背景 随着HarmonyOS 5.0对Web兼容层的增强&#xff0c;React Native作为跨平台框架可通过重新编译ArkTS组件实现85%以上的代码复用率。阅读类应用具有UI复杂度低、数据流清晰的特点。 二、核心实现方案 1. 环境配置 &#xff08;1&#xff09;使用React Native…...

工程地质软件市场:发展现状、趋势与策略建议

一、引言 在工程建设领域&#xff0c;准确把握地质条件是确保项目顺利推进和安全运营的关键。工程地质软件作为处理、分析、模拟和展示工程地质数据的重要工具&#xff0c;正发挥着日益重要的作用。它凭借强大的数据处理能力、三维建模功能、空间分析工具和可视化展示手段&…...

镜像里切换为普通用户

如果你登录远程虚拟机默认就是 root 用户&#xff0c;但你不希望用 root 权限运行 ns-3&#xff08;这是对的&#xff0c;ns3 工具会拒绝 root&#xff09;&#xff0c;你可以按以下方法创建一个 非 root 用户账号 并切换到它运行 ns-3。 一次性解决方案&#xff1a;创建非 roo…...

汇编常见指令

汇编常见指令 一、数据传送指令 指令功能示例说明MOV数据传送MOV EAX, 10将立即数 10 送入 EAXMOV [EBX], EAX将 EAX 值存入 EBX 指向的内存LEA加载有效地址LEA EAX, [EBX4]将 EBX4 的地址存入 EAX&#xff08;不访问内存&#xff09;XCHG交换数据XCHG EAX, EBX交换 EAX 和 EB…...

【C++从零实现Json-Rpc框架】第六弹 —— 服务端模块划分

一、项目背景回顾 前五弹完成了Json-Rpc协议解析、请求处理、客户端调用等基础模块搭建。 本弹重点聚焦于服务端的模块划分与架构设计&#xff0c;提升代码结构的可维护性与扩展性。 二、服务端模块设计目标 高内聚低耦合&#xff1a;各模块职责清晰&#xff0c;便于独立开发…...

RNN避坑指南:从数学推导到LSTM/GRU工业级部署实战流程

本文较长&#xff0c;建议点赞收藏&#xff0c;以免遗失。更多AI大模型应用开发学习视频及资料&#xff0c;尽在聚客AI学院。 本文全面剖析RNN核心原理&#xff0c;深入讲解梯度消失/爆炸问题&#xff0c;并通过LSTM/GRU结构实现解决方案&#xff0c;提供时间序列预测和文本生成…...

【分享】推荐一些办公小工具

1、PDF 在线转换 https://smallpdf.com/cn/pdf-tools 推荐理由&#xff1a;大部分的转换软件需要收费&#xff0c;要么功能不齐全&#xff0c;而开会员又用不了几次浪费钱&#xff0c;借用别人的又不安全。 这个网站它不需要登录或下载安装。而且提供的免费功能就能满足日常…...