算法刷题【二分法】

题目:

在这里插入图片描述
在这里插入图片描述

  • 注意题目中说明了数据时非递减的,那么这样就存在二分性,能够实现logn的复杂度。
  • 二分法每次只能取寻找特定的某一个值,所以我们要分别求左端点和有端点。

分析第一组用例得到结果如下:
在这里插入图片描述
成功找到左端点8


由此可知,用二分法去寻找左端端点的时候:

  • num[mid]<target,那么此时mid的左边包括自身的值都小于target,所以直接执行赋值操作left = mid + 1即可。

  • num[mid]= =target的时候,由于可能此时的mid已经是左端端点了。但是只是可能是左端点了,也有可能不是左端点,所以相等的情况就要和大于的情况合并起来操作,执行right = mid操作。

  • num[mid]>target的时候,mid的右边包括自身都比target的值要大,执行right = mid具有合理性,不能执行right = mid -1因为此时和等于合并起来了,判断条件变成是num[mid] <= target在等于的情况下,可能成为左端的端点。
    图示*😗
    在这里插入图片描述
    上述就是找最左边的端点的基本思路了,但是我们还有一些细节需要处理:

  • 对于每次mid位置的取发:
    1:mid = left + (right-left)/2
    2:mid = left + (right-left +1)/2
    有以上两种取法,前后者在奇数的情况下相同,但是在偶数的情况下就会有所不同。
    偶数的情况下,1会取到中间两个数的片左边的那一个,2会取到中间两个数的偏右边那一个。

对于取左边端点来说:

到最终可能会有这么一种的情况:
在这里插入图片描述
所以在用二分法寻找左侧端点的时候,应该要使用mid的第一种取法(mid = left + (right-left)/2 )。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/349429.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Spring Boot集成 Spring Retry 实现容错重试机制并附源码

&#x1f604; 19年之后由于某些原因断更了三年&#xff0c;23年重新扬帆起航&#xff0c;推出更多优质博文&#xff0c;希望大家多多支持&#xff5e; &#x1f337; 古之立大事者&#xff0c;不惟有超世之才&#xff0c;亦必有坚忍不拔之志 &#x1f390; 个人CSND主页——Mi…

verilog阻塞和非阻塞语法

阻塞和非阻塞是FPGA硬件编程中需要了解的一个概念,绝大部分时候,因为非阻塞的方式更加符合时序逻辑设计的思想,有利于时钟和信号的同步,更加有利于时序收敛,所以除非特殊情况,尽量采用非阻塞方式。 1,非阻塞代码 非阻塞赋值,A和B是同时被赋值的,具体是说在时钟的上升…

论文阅读:H-ViT,一种用于医学图像配准的层级化ViT

来自CVPR的一篇文章&#xff0c;https://openaccess.thecvf.com/content/CVPR2024/papers/Ghahremani_H-ViT_A_Hierarchical_Vision_Transformer_for_Deformable_Image_Registration_CVPR_2024_paper.pdf 用CNNTransformer混合模型做图像配准。可变形图像配准是一种在相同视场…

基于单片机的机械手臂控制系统设计

摘 要&#xff1a; 应用单片机 、 Arduino 及机械臂的有关知识&#xff0c;设计一款基于单片机的六自由度机械手臂&#xff0c;并详述其控制系统的软、 硬件设计 。 该机械手臂能够模仿人的上肢完成简单的动作&#xff0c;因此在实验教学演示平台 、 生产或生活中都极具应用价…

Dubbo 3.x源码(20)—Dubbo服务引用源码(3)

基于Dubbo 3.1&#xff0c;详细介绍了Dubbo服务的发布与引用的源码。 此前我们学习了调用createProxy方法&#xff0c;根据服务引用参数map创建服务接口代理引用对象的整体流程&#xff0c;我们知道会调用createInvokerForRemote方法创建远程引用Invoker&#xff0c;这是Dubbo …

Linux文件系统

目录 1.磁盘的结构 1.1磁盘的物理结构 1.2 磁盘的存储结构 1.3 磁盘的逻辑结构 2.文件系统 在上一篇文章基础IO中&#xff0c;我们主要是讲了被打开的文件与进程的关系&#xff0c;以及操作系统是如何管理这些被打开的文件的&#xff0c;但是磁盘有这么多文件&#xff0c;被打…

QT--DAY1

不使用图形化界面实现一个登陆界面 #include "widget.h"Widget::Widget(QWidget *parent): QWidget(parent) {//设置窗口标题this->setWindowTitle("登录界面");//设置窗口大小this->resize(535,410);//固定窗口大小this->setFixedSize(535,410)…

windows 环境下使用git命令导出差异化文件及目录

一、找出差异化的版本&#xff08;再此使用idea的show history&#xff09; 找到两个提交记录的id 分别为&#xff1a; 二、使用git bash执行命令&#xff08;主要使用 tar命令压缩文件&#xff09; 输出结果&#xff1a;

上心师傅的思路分享(三)--Nacos渗透

目录 1. 前言 2. Nacos 2.1 Nacos介绍 2.2 鹰图语法 2.3 fofa语法 2.3 漏洞列表 未授权API接口漏洞 3 环境搭建 3.1 方式一: 3.2 方式二: 3.3 访问方式 4. 工具监测 5. 漏洞复现 5.1 弱口令 5.2 未授权接口 5.3.1 用户信息 API 5.3.2 集群信息 API 5.3.3 配置…

kubernetes(k8s)集群部署(2)

目录 k8s集群类型 k8s集群规划&#xff1a; 1.基础环境准备&#xff1a; &#xff08;1&#xff09;保证可以连接外网 &#xff08;2&#xff09;关闭禁用防火墙和selinux &#xff08;3&#xff09;同步阿里云服务器时间&#xff08;达到集群之间时间同步&#xff09; &…

pytest并发执行时token异常处理问题

接前面加入钩子函数处理token复用的问题&#xff0c;只保证了用例的串联执行&#xff0c;我的部分测试用例中接入了通义千问的部分接口生成测试数据&#xff0c;七八个场景跑完差不多快要10分钟。考虑使用并发执行。 http://t.csdnimg.cn/ACexL 使用多线程和不使用耗时差距很大…

HyperBDR新版本上线,自动化容灾兼容再升级!

本次HyperBDR v5.5.0版本新增完成HCS&#xff08;Huawei Cloud Stack&#xff09;8.3.x和HCSO&#xff08;Huawei Cloud Stack Online&#xff09;自动化对接&#xff0c;另外还突破性完成了Oracle云(块存储模式)的自动化对接。 HyperBDR&#xff0c;云原生业务级别容灾工具。支…

Unity资源 之 最受欢迎的三消游戏开发包 - Bubble Shooter Kit 【免费领取】

三消游戏开发包 - Bubble Shooter Kit 免费领取 前言资源包内容领取兑换码 前言 如果你是一名 Unity 游戏开发者&#xff0c;并且正在寻找一种快速、简单的方式来创建自己的三消游戏&#xff0c;那么 Bubble Shooter Kit 就是你所需要的。 资源包内容 Bubble Shooter Kit 是…

代码随想录算法训练营第36期 last day

最后一次更新&#xff0c;之后去复习专业课和简历 583两个字符串的删除操作 自己做出来了&#xff1a; Code: class Solution {public://找到公共子序列的最大长度dp 最小步数串1.size-dp串2.size-dp int minDistance(string word1, string word2) { vector<v…

用智能插件(Fitten Code: Faster and Better AI Assistant)再次修改vue3 <script setup>留言板

<template><div><button class"openForm" click"openForm" v-if"!formVisible">编辑</button><button click"closeForm" v-if"formVisible">取消编辑</button><hr /><formv-i…

基于梯度下降的多元线性回归原理

为了展示多元线性回归的迭代过程&#xff0c;我们可以使用梯度下降算法手动实现多元线性回归。梯度下降是一种迭代优化算法&#xff0c;用于最小化损失函数。 我们将以下步骤进行手动实现&#xff1a; 初始化回归系数。计算预测值和损失函数。计算梯度。更新回归系数。重复步…

高分论文密码---大尺度空间模拟预测与数字制图

大尺度空间模拟预测和数字制图技术和不确定性分析广泛应用于高分SCI论文之中&#xff0c;号称高分论文密码。大尺度模拟技术可以从不同时空尺度阐明农业生态环境领域的内在机理和时空变化规律&#xff0c;又可以为复杂的机理过程模型大尺度模拟提供技术基础。我们将结合一些经典…

制造业几大系统(MES/WMS/QMS/ERP)的集成

制造业的几大系统包括MES&#xff08;制造执行系统&#xff09;、WMS&#xff08;仓库管理系统&#xff09;、QMS&#xff08;质量管理系统&#xff09;和ERP&#xff08;企业资源计划&#xff09;系统。这些系统在制造业中扮演着不同的角色&#xff0c;可以通过集成实现更高效…

Kafka高频面试题整理

文章目录 1、什么是Kafka?2、kafka基本概念3、工作流程4、Kafka的数据模型与消息存储机制1)索引文件2)数据文件 5、ACKS 机制6、生产者重试机制:7、kafka是pull还是push8、kafka高性能高吞吐的原因1&#xff09;磁盘顺序读写&#xff1a;保证了消息的堆积2&#xff09;零拷贝机…

SqlSugar有实体CURD应用-C#

本文所述开发环境&#xff1a;.C#、NET8、Visual Studio2022 SqlSugar有实体查询数据表 首先根据《SqlSugar使用DbFirst对象根据数据库表结构创建实体类-C#》中的描述的表结构创建所有表的实体类如下&#xff1a; 表名创建的实体类名tb_studentStudenttb_teacherTeachertb_c…