【二分查找】——模板
二分查找模板题
一、题目要求
给定一个长度为n的非递减数组和一个数字target,要求找到数组中第一个大于等于target的位置pos,数组下标从 0 开始。如果不存在大于等于target的数字,则输出 -1。
二、输入格式
- 第一行:为两个正整数
n和target,其中1≤n,target≤10^5。分别表示数组长度和要查询的数字。 - 第二行:为
n个正整数a1,a2,...,an,其中1≤ai≤10^5,表示给定的非递减数组。
三、输出格式
输出数组中第一个大于等于target的位置pos,如果不存在,则输出 -1。
四、示例
- 输入:
7 52 3 5 6 7 8 9
- 输出:
2
暴力解法
一个一个试
二分查找
二分查找代码思路的通俗解释:
一、整体目标
我们的目标是在一个非递减(升序)的整数数组中找到第一个大于等于给定目标值target的元素的位置。如果不存在这样的元素,则返回 -1。
二、初始化
- 首先,我们有一个整数数组
nums,它的长度为n。我们设置两个指针,left指向数组的第一个元素的位置,初始值为 0;right指向数组的最后一个元素的位置,初始值为n - 1。- 这就好比我们在一个有很多房间的长廊里找东西,一开始
left站在第一个房间门口,right站在最后一个房间门口,确定了我们的搜索范围是整个长廊。
- 这就好比我们在一个有很多房间的长廊里找东西,一开始
三、循环查找
- 进入一个循环,只要
left小于right,就一直循环下去。- 这个循环就像是我们在不断缩小搜索范围,直到找到目标或者确定目标不存在。
- 在循环中,计算中间位置
mid,计算公式是mid = left + (right - left) // 2。- 这就相当于我们每次都把长廊分成两部分,然后去中间的那个房间看看。
- 如果中间位置的元素
nums[mid]小于目标值target,说明目标值如果存在的话,一定在mid的右边。所以我们把left更新为mid + 1,这样就缩小了搜索范围到右边的部分。- 就像我们确定目标不在左边这一半长廊了,于是
left走到了原来中间那个房间的右边一个房间,继续搜索右边的长廊。
- 就像我们确定目标不在左边这一半长廊了,于是
- 如果中间位置的元素
nums[mid]大于等于目标值target,说明目标值如果存在的话,一定在mid的左边或者就是mid本身。所以我们把right更新为mid,这样就缩小了搜索范围到左边的部分。- 这时候我们觉得目标可能在左边这一半长廊,于是
right走到了原来中间那个房间,继续搜索左边的长廊。
- 这时候我们觉得目标可能在左边这一半长廊,于是
四、确定结果
- 当循环结束时,也就是
left和right相等或者left大于right了。这时候我们检查left位置的元素是否大于等于目标值。- 如果是,说明我们找到了第一个大于等于目标值的位置,就是
left。 - 如果不是,说明数组中不存在大于等于目标值的元素,就返回 -1。
- 如果是,说明我们找到了第一个大于等于目标值的位置,就是
n, target = map(int, input().split())
nums = list(map(int, input().split()))left, right = 0, n - 1
while left < right:mid = left + (right - left) // 2if nums[mid] < target:left = mid + 1else:right = mid
if nums[left] >= target:print(left)
else:print(-1)
二分查找适用于以下几种情况:
- 有序数据查找元素:数据是有序排列的,要查找特定元素,能高效定位,时间复杂度为 O ( l o g n ) O(log n) O(logn),比线性查找的 O ( n ) O(n) O(n)快很多。
- 查找边界值:在单调变化(递增或递减)的数据中,找满足某个条件的边界值,比如满足某个不等式的最小或最大数值。
- 动态规划优化:在动态规划问题里,用于优化状态转移过程,快速查找满足条件的区间内元素。
- 广范围数据搜索:数据分布范围广,二分查找可以缩小搜索区间,快速定位目标或目标区间,避免大量无效搜索。
相关文章:
【二分查找】——模板
二分查找模板题 一、题目要求 给定一个长度为n的非递减数组和一个数字target,要求找到数组中第一个大于等于target的位置pos,数组下标从 0 开始。如果不存在大于等于target的数字,则输出 -1。 二、输入格式 第一行:为两个正整…...
从可逆计算看DSL的设计要点
低代码平台的可视化设计器本质上是DSL(Domain Specific Language)的结构化编辑器。可视化设计器将编辑的结果序列化成文本格式时所采用的规范就是一种DSL语法定义。 Nop平台基于可逆计算原理,提出了一整套系统化的构建机制来简化DSL的设计和…...
axios竟态问题
竟态问题 在我们日常开发经常遇到一些竟态问题 例子1 现象1 表格分页,如果设置请求loading, 先切换到分页第99页,迅速在又切换到第1页,最后列表显示的是第99页数据。 原因 由于第99页请求数据花费时间可能500ms,第1页数据只需要100ms,第1页…...
如何批量注册多个Outlook邮箱账号并避免关联
批量注册多个Outlook邮箱账号时,如何避免账号之间的关联性是一个重要的考量因素。会在此文一起探讨如何高效且安全地批量注册多个Outlook邮箱账号,并提供一些实用的建议来确保这些账号不会被关联。 一、Outlook邮箱批量注册机制 在深入注册流程之前&…...
如何在安卓設備上設置全局代理?
對於安卓用戶來說,設置全局代理是維護網路隱私一種有效的方法,可以幫助在所有應用中使用同一個代理伺服器。本文將詳細介紹如何在安卓設備上進行全局代理設置。全局代理指的是通過一個代理伺服器來轉發設備上所有應用程式的網路請求。這樣,所…...
操作系统实验记录
实验零:虚拟机安装 一、安装vmware虚拟机 与vmware匹配搜索结果 - 考拉软件 (rjctx.com),下载17.5.1版本即可下载后对照教程安装 二、下载iso虚拟驱动 搜索清华大学镜像网站,点击再搜ubuntu,下载这个4.1GB的iso文件安装后打开vmware虚拟机 三、配置vmware虚拟机 右键管…...
FastAPI 路径参数详解:动态路径与数据校验的灵活实现
FastAPI 路径参数详解:动态路径与数据校验的灵活实现 本文全面介绍了在 FastAPI 中使用路径参数的技巧和实现方式。路径参数允许 API 动态响应不同路径中的请求信息,结合 URL(Uniform Resource Locator)和 URI(Unifor…...
【STM32】SD卡
(一)常用卡的认识 在学习这个内容之前,作为生活小白的我对于SD卡、TF卡、SIM卡毫无了解,晕头转向。 SD卡:Secure Digital Card的英文缩写,直译就是“安全数字卡”。一般用于大一些的电子设备比如:电脑、数码相机、AV…...
我一口气记录下整个接口自动化测试过程!
一、为什么选用postman postman调试工具无论对于开发和测试小白,还是技术大牛来说应该都耳熟能详,在过去的几年里大家对这款工具应用最广的用途是把当作接口调试的测试工具,它能发送几乎所有类型的HTTP请求,操作界面非常简洁美观…...
【VS中Git同步提交 报错:访问.vs/FileContentIndex/xxx.vsidx权限不允许】
参考: Git commit vsidx file access denied in Visual Studio 一劳永逸的方法: 在VSCode里,Git->设置->选项:编辑.gitignore文件,如下图: 忽略整个.vs文件夹,再重新提交就不会有涉及…...
Linux下Nginx的安装与使用
Linux下Nginx的安装与使用 博客: www.lstar.icu 开源地址 Gitee 地址: https://gitee.com/lxwise/iris-blog_parent Github 地址: https://github.com/lxwise/iris-blog_parent 序言 Nginx是一款轻量级的Web 服务器/反向代理服务器及电子…...
飞机布雷盖航程公式
飞机布雷盖航程公式 1. 喷气式飞机布雷盖航程公式推导2. 螺旋桨飞机布雷盖航程公式推导3. 喷气式飞机与螺旋桨飞机的差异分析3.1 喷气式飞机的推力产生机制3.2 螺旋桨推进推力产生机制 布雷盖航程公式(Breguet Range Equation)是描述飞行器巡航飞行阶段航…...
在K8s平台部署个人博客
在K8s平台部署个人博客 实验步骤查看wordpress前端的service浏览器访问http://node_ip:30090 实验步骤 kubectl create secret generic mysql-pass --from-literalpasswordYOUR_PASSWORD把mysql.tar.gz和wordpress.tar.gz上传到K8s工作节点,手动解压即可࿱…...
git入门教程10:git性能优化
一、配置优化 使用SSH协议: 相比HTTP/HTTPS协议,SSH协议在网络传输中更高效,且支持更安全的认证方式。确保你的远程仓库URL使用的是SSH协议,例如:git clone gitgithub.com:username/repo.git。 调整Git缓冲区大小&…...
Redis(2):内存模型
一、Redis内存统计 工欲善其事必先利其器,在说明Redis内存之前首先说明如何统计Redis使用内存的情况。 在客户端通过redis-cli连接服务器后(后面如无特殊说明,客户端一律使用redis-cli),通过info命令可以查看内存使用情…...
深入解析Diffusion和AsymmDiT:Mochi 1的高效AI视频生成之路
随着AI视频生成技术的迅猛发展,各种模型纷纷涌现,各自展现出独特的优势。近期,Genmo 推出了新一代视频生成模型——Mochi 1,以其非对称架构设计和高效生成流程在业界备受瞩目。作为开源模型,Mochi 1不仅在视觉生成质量…...
VMware capacity mismatch for disk错误解决办法:kb-vuln-1靶机
https://www.vulnhub.com/entry/kb-vuln-1,540/ 本机安装有: VMware Workstation 16 Pro 16.2.1 build-18811642VirtualBox 图形用户界面 版本 5.2.30 r130521 (Qt5.6.2) vm16.2支持wsl2,所以我得让vm16.2跑靶机,VirtualBox5.2可以导入靶机,但是无法开机(不支持wsl2),得升级 …...
Java Collection/Executor LinkedTransferQueue 总结
前言 相关系列 《Java & Collection & 目录》《Java & Executor & 目录》《Java & Collection/Executor & LinkedTransferQueue & 源码》《Java & Collection/Executor & LinkedTransferQueue & 总结》《Java & Collection/Execu…...
阿拉伯国家本地化测试的特点
针对阿拉伯国家的应用程序的本地化测试需要详细了解语言、文化背景、地区规范和技术细节,以符合阿拉伯语用户的期望。这些国家包括沙特阿拉伯、阿拉伯联合酋长国、科威特、卡塔尔、巴林和阿曼,具有独特的语言和文化因素,成功地本地化测试解决…...
申请前必知!关于「美国绿卡」的28个常见问题汇总!
01 美国绿卡的类别 美国绿卡分为多个类别,如亲属移民、职业移民、投资移民等。每个类别有不同的申请要求和优先级。选择最适合自己的类别,并深入了解相关法律和政策,是成功申请的第一步。 02 移民路径选择 根据个人情况(如职业…...
ES6从入门到精通:前言
ES6简介 ES6(ECMAScript 2015)是JavaScript语言的重大更新,引入了许多新特性,包括语法糖、新数据类型、模块化支持等,显著提升了开发效率和代码可维护性。 核心知识点概览 变量声明 let 和 const 取代 var…...
23-Oracle 23 ai 区块链表(Blockchain Table)
小伙伴有没有在金融强合规的领域中遇见,必须要保持数据不可变,管理员都无法修改和留痕的要求。比如医疗的电子病历中,影像检查检验结果不可篡改行的,药品追溯过程中数据只可插入无法删除的特性需求;登录日志、修改日志…...
CentOS下的分布式内存计算Spark环境部署
一、Spark 核心架构与应用场景 1.1 分布式计算引擎的核心优势 Spark 是基于内存的分布式计算框架,相比 MapReduce 具有以下核心优势: 内存计算:数据可常驻内存,迭代计算性能提升 10-100 倍(文档段落:3-79…...
使用van-uploader 的UI组件,结合vue2如何实现图片上传组件的封装
以下是基于 vant-ui(适配 Vue2 版本 )实现截图中照片上传预览、删除功能,并封装成可复用组件的完整代码,包含样式和逻辑实现,可直接在 Vue2 项目中使用: 1. 封装的图片上传组件 ImageUploader.vue <te…...
Unit 1 深度强化学习简介
Deep RL Course ——Unit 1 Introduction 从理论和实践层面深入学习深度强化学习。学会使用知名的深度强化学习库,例如 Stable Baselines3、RL Baselines3 Zoo、Sample Factory 和 CleanRL。在独特的环境中训练智能体,比如 SnowballFight、Huggy the Do…...
华为云Flexus+DeepSeek征文|DeepSeek-V3/R1 商用服务开通全流程与本地部署搭建
华为云FlexusDeepSeek征文|DeepSeek-V3/R1 商用服务开通全流程与本地部署搭建 前言 如今大模型其性能出色,华为云 ModelArts Studio_MaaS大模型即服务平台华为云内置了大模型,能助力我们轻松驾驭 DeepSeek-V3/R1,本文中将分享如何…...
Java多线程实现之Thread类深度解析
Java多线程实现之Thread类深度解析 一、多线程基础概念1.1 什么是线程1.2 多线程的优势1.3 Java多线程模型 二、Thread类的基本结构与构造函数2.1 Thread类的继承关系2.2 构造函数 三、创建和启动线程3.1 继承Thread类创建线程3.2 实现Runnable接口创建线程 四、Thread类的核心…...
关键领域软件测试的突围之路:如何破解安全与效率的平衡难题
在数字化浪潮席卷全球的今天,软件系统已成为国家关键领域的核心战斗力。不同于普通商业软件,这些承载着国家安全使命的软件系统面临着前所未有的质量挑战——如何在确保绝对安全的前提下,实现高效测试与快速迭代?这一命题正考验着…...
sipsak:SIP瑞士军刀!全参数详细教程!Kali Linux教程!
简介 sipsak 是一个面向会话初始协议 (SIP) 应用程序开发人员和管理员的小型命令行工具。它可以用于对 SIP 应用程序和设备进行一些简单的测试。 sipsak 是一款 SIP 压力和诊断实用程序。它通过 sip-uri 向服务器发送 SIP 请求,并检查收到的响应。它以以下模式之一…...
淘宝扭蛋机小程序系统开发:打造互动性强的购物平台
淘宝扭蛋机小程序系统的开发,旨在打造一个互动性强的购物平台,让用户在购物的同时,能够享受到更多的乐趣和惊喜。 淘宝扭蛋机小程序系统拥有丰富的互动功能。用户可以通过虚拟摇杆操作扭蛋机,实现旋转、抽拉等动作,增…...
