算法刷题【二分法】

题目:

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

  • 注意题目中说明了数据时非递减的,那么这样就存在二分性,能够实现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 )。

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

Autosar Dem配置-Condition(TRC)的使用-基于ETAS软件

文章目录 前言Dem配置DemEnableConditionDemEnableConditionIdDemEnableConditionStatus DemEnableConditionGroupDemEventParameter 接口配置代码实现总结 前言 在车辆工作状态下&#xff0c;每个DTC检测可能都需要一个前提条件&#xff0c;否则如果任何条件下都可以进行DTC检…

C# WPF入门学习主线篇(十七)—— UniformGrid布局容器

C# WPF入门学习主线篇&#xff08;十七&#xff09;—— UniformGrid布局容器 欢迎来到C# WPF入门学习系列的第十七篇。在前几篇文章中&#xff0c;我们已经探讨了 Canvas、StackPanel、WrapPanel、DockPanel 和 Grid 布局容器及其使用方法。本篇博客将介绍另一种非常实用且简单…

coap-emqx:使用libcoap与emqx通信

# emqx开启CoAP网关 请参考【https://blog.csdn.net/chenhz2284/article/details/139562749?spm1001.2014.3001.5502】 # 写一个emqx的客户端程序&#xff0c;不断地往topic【server/1】发消息 【pom.xml】 <dependency><groupId>org.springframework.boot<…

一分钟学习数据安全—自主管理身份SSI加密技术

上篇介绍了SSI的架构。架构之后&#xff0c;我们要了解一下SSI发展的驱动力&#xff1a;加密技术。现代数字通信离不开数学和计算机科学&#xff0c;加密技术也源于此。加密技术使区块链和分布式账本得以实现&#xff0c;也使SSI成为可能。 以下我们就概览一下SSI基础架构中涉及…

Python实现半双工的实时通信SSE(Server-Sent Events)

Python实现半双工的实时通信SSE&#xff08;Server-Sent Events&#xff09; 1 简介 实现实时通信一般有WebSocket、Socket.IO和SSE&#xff08;Server-Sent Events&#xff09;三种方法。WebSocket和Socket.IO是全双工的实时双向通信技术&#xff0c;适合用于聊天和会话等&a…

微信小程序学习笔记(1)

文章目录 一、文件作用app.json&#xff1a;project.config.json:sitemap.json页面中.json 二、项目首页三、语法**WXML**和**HTML**WXSS 和CSS的区别小程序中.js文件的分类 一、文件作用 app.json&#xff1a; 当前小程序的全局配置&#xff0c;包括所有页面路径、窗口外观、…

kv视频如何转码mp4格式,kv转换mp4最简单方法

在数字化时代&#xff0c;视频格式转换成为了一项日常需求。有时候我们需要把kv格式转换为MP4格式。下面将详细介绍kv转MP4的方法 方法一、 1、使用 "小白兔视频格式在线转换网站" 2、地址发给"小白兔视频格式在线转换网站"的客服&#xff0c;客服下载即可…

基于小波脊线的一维时间序列信号分解方法(MATLAB R2018A)

信号分解技术是把一个复杂信号分解为若干含有时频信息的简单信号&#xff0c;研可通过分解后的简单信号来读取和分析复杂信号的有效特征。因此&#xff0c;信号分解技术对分析结果的影响是不言而喻的。 傅里叶分解是早期常用的信号分解方法&#xff0c;最初被用于分析热过程&a…

树状数组的基础

树状数组1 树状数组可以解决什么问题呢&#xff1f; 可以解决大部分区间上面的修改以及查询的问题&#xff0c;例如1.单点修改&#xff0c;单点查询&#xff0c;2.区间修改&#xff0c;单点查询&#xff0c;3.区间查询&#xff0c;区间修改&#xff0c;换言之&#xff0c;线段…

分享一个用python写的本地WIFI密码查看器

本章教程&#xff0c;主要分享一个本地wifi密码查看器&#xff0c;用python实现的&#xff0c;感兴趣的可以试一试。 具体代码 import subprocess # 导入 subprocess 模块&#xff0c;用于执行系统命令 import tkinter as tk # 导入 tkinter 模块&#xff0c;用于创建图形用…

达梦8 开启物理逻辑日志对系统的影响

物理逻辑日志&#xff0c;是按照特定的格式存储的服务器的逻辑操作&#xff0c;专门用于 DBMS_LOGMNR 包挖掘获取数据库系统的历史执行语句。当开启记录物理逻辑日志的功能时&#xff0c;这部分日志内 容会被存储在重做日志文件中。 要开启物理逻辑日志的功能&#xff0c;需要…

如何将AndroidStudio和IDEA的包名改为分层级目录

新版UIAndroidStudio 1、点击项目目录右上角如图所示的三个点点。 2、然后依次取消Hide empty middle package &#xff0c;Flatten package的勾选 3、注意&#xff1a;一定要先取消hide的勾选&#xff0c;不然目录不会完全分级&#xff08;做错了可以反过来重新设置&#x…

VS2019专业版 C#和MFC安装

1. VS2019专业版下载地址 https://learn.microsoft.com/en-us/visualstudio/releases/2019/history 2.安装 C# 部分 MFC部分

利用SuperGlue算法实现跨尺度金字塔特征点的高效匹配(含py代码)

在计算机视觉领域&#xff0c;特征点匹配是一个基础而关键的任务&#xff0c;广泛应用于图像拼接、三维重建、目标跟踪等方向。传统的特征点匹配方法通常基于相同尺度下提取的特征进行匹配&#xff0c;然而在实际场景中&#xff0c;由于成像距离、分辨率等因素的差异&#xff0…

【个人博客搭建练手版】Windows环境下使用tale,mblog,halo三种框架搭建个人博客,适合准备搭建博客的练手之作

昨天发了一篇搭建博客的教程&#xff0c;竟然上新人榜了。 博客链接&#xff1a;https://editor.csdn.net/md/?articleId139392436 趁热打铁把该文章中说的使用在Windows环境使用docker desktop搭建halo博客练手的教程也写一下。 这篇文章不只有halo的搭建&#xff0c;还有ta…

堆排序讲解

前言 在讲堆的删除时&#xff0c;我们发现一步一步删除堆顶的数据&#xff0c;排列起来呈现出排序的规律&#xff0c;所以本节小编将带领大家进一步理解堆排序。 1.堆排序概念 那么什么是堆排序&#xff1f; 堆排序&#xff08;Heap Sort&#xff09;是一种基于堆数据结构的排…

JS-Fetch

Fetch 是一种用于进行网络请求的现代 JavaScript API。它提供了一种简单、灵活且功能强大的方式&#xff0c;用于从服务器获取资源并处理响应。 Fetch API 在浏览器中原生支持&#xff0c;并且以 Promise 为基础&#xff0c;使得异步请求更加直观和易用。使用 Fetch API&#…

C++ Qt实现http url启动本地应用程序

更多Qt文章,请访问《深入浅出C++ Qt开发技术专栏》:https://blog.csdn.net/yao_hou/category_9276099.html 文章目录 1、注册自定义协议2、编写web页面3、编写C++应用程序我们在使用腾讯会议时经常会通过http链接打开本地的腾讯会议,例如下图: 打开会议发起人给的链接,会出…

C语言小例程10/100

题目&#xff1a;要求输出国际象棋棋盘。 程序分析&#xff1a;国际象棋棋盘由64个黑白相间的格子组成&#xff0c;分为8行*8列。用i控制行&#xff0c;j来控制列&#xff0c;根据ij的和的变化来控制输出黑方格&#xff0c;还是白方格。 #include<stdio.h>int main() {…

Elasticsearch:ES|QL 查询 TypeScript 类型(二)

在我之前的文章 “Elasticsearch&#xff1a;ES|QL 查询 TypeScript 类型&#xff08;一&#xff09;”&#xff0c;我们讲述了如何在 Nodejs 里对 ES|QL 进行查询。在今天的文章中&#xff0c;我们来使用一个完整的例子来进行详细描述。更多有关如何使用 Nodejs 来访问 Elasti…