LeetCode-704. 二分查找【数组 二分查找】
LeetCode-704. 二分查找【数组 二分查找】
- 题目描述:
- 解题思路一:注意开区间和闭区间
- 背诵版:
- 解题思路三:
题目描述:
给定一个 n 个元素有序的(升序)整型数组 nums 和一个目标值 target ,写一个函数搜索 nums 中的 target,如果目标值存在返回下标,否则返回 -1。
示例 1:
输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4
示例 2:
输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1
提示:
你可以假设 nums 中的所有元素是不重复的。
n 将在 [1, 10000]之间。
nums 的每个元素都将在 [-9999, 9999]之间。
解题思路一:注意开区间和闭区间
# lower_bound 返回最小的满足 nums[i] >= target 的 i
# 如果数组为空,或者所有数都 < target,则返回 len(nums)
# 要求 nums 是非递减的,即 nums[i] <= nums[i + 1]# 闭区间写法
def lower_bound(nums: List[int], target: int) -> int:left, right = 0, len(nums) - 1 # 闭区间 [left, right]while left <= right: # 区间不为空# 循环不变量:# nums[left-1] < target# nums[right+1] >= targetmid = (left + right) // 2if nums[mid] < target:left = mid + 1 # 范围缩小到 [mid+1, right]else:right = mid - 1 # 范围缩小到 [left, mid-1]return left # 或者 right+1# 左闭右开区间写法
def lower_bound2(nums: List[int], target: int) -> int:left, right = 0, len(nums) # 左闭右开区间 [left, right)while left < right: # 区间不为空# 循环不变量:# nums[left-1] < target# nums[right] >= targetmid = (left + right) // 2if nums[mid] < target:left = mid + 1 # 范围缩小到 [mid+1, right)else:right = mid # 范围缩小到 [left, mid)return left # 或者 right# 开区间写法
def lower_bound3(nums: List[int], target: int) -> int:left, right = -1, len(nums) # 开区间 (left, right)while left + 1 < right: # 区间不为空mid = (left + right) // 2# 循环不变量:# nums[left] < target# nums[right] >= targetif nums[mid] < target:left = mid # 范围缩小到 (mid, right)else:right = mid # 范围缩小到 (left, mid)return right # 或者 left+1class Solution:def search(self, nums: List[int], target: int) -> int:i = lower_bound(nums, target) # 选择其中一种写法即可return i if i < len(nums) and nums[i] == target else -1
时间复杂度:O(logn)
空间复杂度:O(1)
背诵版:
class Solution:def search(self, nums: List[int], target: int) -> int:l = 0r = len(nums) - 1while l <= r:mid = (l + r) // 2if nums[mid] > target:r = mid - 1elif nums[mid] < target:l = mid + 1else:return midreturn -1
时间复杂度:O(logn)
空间复杂度:O(1)
解题思路三:
时间复杂度:O(logn)
空间复杂度:O(1)


♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠
相关文章:
LeetCode-704. 二分查找【数组 二分查找】
LeetCode-704. 二分查找【数组 二分查找】 题目描述:解题思路一:注意开区间和闭区间背诵版:解题思路三: 题目描述: 给定一个 n 个元素有序的(升序)整型数组 nums 和一个目标值 target …...
Rust 性能分析
都说Rust性能好,但是也得代码写得好,猜猜下面两个代码哪个快 . - 力扣(LeetCode) use std::collections::HashMap; use lazy_static::lazy_static;lazy_static! {static ref DIGIT: HashMap<char, usize> {let mut m HashMap::new();for c in …...
Gradle和Maven都是广泛使用的项目自动化构建工具
Gradle和Maven都是广泛使用的项目自动化构建工具,但它们在多个方面存在差异。以下是关于Gradle和Maven的详细对比: 一、构建脚本语言 Maven:使用XML作为构建脚本语言。XML的语法较为繁琐,不够灵活,对于复杂的构建逻辑…...
Seed-TTS语音编辑有多强?对比实测结果让你惊叹!
GLM-4-9B 开源系列模型 前言 就在最近,ByteDance的研究人员最近推出了一系列名为Seed-TTS的大规模自回归文本转语音(TTS)模型,能够合成几乎与人类语音无法区分的高质量语音。那么Seed-TTS的表现究竟有多强呢?让我们一起来感受下Seed-TTS带来的惊喜吧! 介绍Seed-TTS…...
Vue3——实现word,pdf上传之后,预览功能(实测有效)
vue-office/pdf - npm支持多种文件(**docx、excel、pdf**)预览的vue组件库,支持vue2/3。也支持非Vue框架的预览。. Latest version: 2.0.2, last published: a month ago. Start using vue-office/pdf in your project by running npm i vue-office/pdf. There are …...
JVM之【类的生命周期】
首先,请区分Bean的声明周期和类的声明周期。此处讲的是类的声明周期 可以同步观看另一篇文章JVM之【类加载机制】 概述 在Java中数据类型分为基本数据类型和引用数据类型 基本数据类型由虚拟机预先定义,引用数据类型则需要进行类的加载 按照]ava虚拟机…...
分库分表场景下,如何设计与实现一种高效的分布式ID生成策略
在构建大规模分布式系统时,随着数据量的爆炸式增长,单个数据库往往难以承载如此庞大的数据存储与访问需求。这时,分库分表便成为一种有效的解决方案,它通过将数据分散存储在多个数据库或表中,从而提高系统的处理能力和…...
机器人系统ros2-开发学习实践16-RViz 用户指南
RViz 是 ROS(Robot Operating System)中的一个强大的 3D 可视化工具,用于可视化机器人模型、传感器数据、路径规划等。以下是RViz用户指南,帮助你了解如何使用RViz来进行机器人开发和调试。 启动可视化工具 ros2 run rviz2 rviz2…...
安全测试 之 安全漏洞 CSRF
1. 背景 安全测试是在功能测试的基础上进行的,它验证软件的安全需求,确保产品在遭受恶意攻击时仍能正常运行,并保护用户信息不受侵犯。 2. CSRF 定义 CSRF(Cross-Site Request Forgery),中文名为“跨站请…...
交易中的预测和跟随
任何的交易决策,一定是基于某种推理关系的,这种推理关系是基于t时刻之前的状态,得到t时刻之后的结果,我们基于这种推理关系,根据当前的状态,形成了未来结果的某种预期,然后基于这种预期采取相应…...
vs2022专业版永久密钥
vs2022专业版永久密钥: vs2022专业版永久密钥: Visual Studio 2022 Enterprise:VHF9H-NXBBB-638P6-6JHCY-88JWH Visual Studio 2022 Professional:TD244-P4NB7-YQ6XK-Y8MMM-YWV2J...
MongoDB环境搭建
一.下载安装包 Download MongoDB Community Server | MongoDB 二、双击下载完成后的安装包开始安装,除了以下两个部分需要注意操作,其他直接next就行 三.可视化界面安装 下载MongoDB-compass,地址如下 MongoDB Compass Download (GUI) | M…...
数据结构【队列】
队列的的概念 队列是一种特殊的线性表,特殊之处在于它只允许在表的头部进行删除操作,而在表的尾部进行插入操作,和栈一样,队列是一种操作受限制的线性表。进行插入操作的端称为队尾,进行删除操作的端称为队头。队列中…...
微信小程序上架,AI类目审核(AI问答、AI绘画、AI换脸)
小程序对于生成式AI类目的产品上架审核较为严格,这也是近两年新增了几个类目,一旦小程序中涉及生成式AI相关的内容,如果你选择相应类目,但审核被划归为这一类,都需要准备此类目的审核,才能正常上架。 如果…...
Vue3学习记录(第一天)
Vue3学习记录_第一天 背景说明记录Vue3实现响应式前端的反射前端对象的属性赋值Vue3响应式实现过程稿前端移除对象的属性 背景 本次学习主要是看视频学习, 没有跟练, 但是很多知识点感觉又容易忘记. 所以通过笔记的方式输出一下. 说明 估计只能自己看懂, 如果能提供一些其他…...
springboot+vue+mybatis房屋租贷系统+PPT+论文+讲解+售后
本论文系统地描绘了整个网上房屋租赁系统的设计与实现,主要实现的功能有以下几点:管理员;首页、个人中心、房屋类型管理、房屋租赁管理、会员管理、订单信息管理、合同信息管理、退房评价管理、管理员管理,系统管理,前…...
Day30 登录界面设计
本章节,实现了登录界面窗口设计 一.准备登录界面图片素材(透明背景图片) 把准备好的图片放在 Images 文件夹下面,格式分别是 .png和 .icoico 图片,右键属性,生成操作选 内容 png 图片,右键属性,生成操作选 资源 选中 login.png图片鼠标右键,选择属性。生成的操作选…...
VOJ 迷阵突围 题解 次短路径 dijkstra算法
迷阵突围 题目描述 小明陷入了坐标系上的一个迷阵,迷阵上有 n 个点,编号从 1 到 n 。小明在编号为 1 的位置,他想到编号为 n 的位置上。小明当然想尽快到达目的地,但是他觉得最短的路径可能有风险,所以他会选择第二短…...
Oracle SQL详解
Oracle SQL是一种用于管理和操作Oracle数据库的编程语言。以下是一些基本的Oracle SQL语法和建表建用户的详解。 创建用户 在Oracle中,创建用户通常需要具有足够权限的用户(通常是具有DBA角色的用户)。以下是一个创建用户的例子:…...
产业,到底需要什么大模型?
[ 产业究竟需要怎样的大模型?关于这个问题,本文作者便提出了他的看法,并总结了产业大模型目前阶段的三点落地挑战。一起来看看,或许可以帮助你更好地理解大模型与行业、与产业的融合。 写下这篇的起因,是前不久的一件事…...
2025年能源电力系统与流体力学国际会议 (EPSFD 2025)
2025年能源电力系统与流体力学国际会议(EPSFD 2025)将于本年度在美丽的杭州盛大召开。作为全球能源、电力系统以及流体力学领域的顶级盛会,EPSFD 2025旨在为来自世界各地的科学家、工程师和研究人员提供一个展示最新研究成果、分享实践经验及…...
学校招生小程序源码介绍
基于ThinkPHPFastAdminUniApp开发的学校招生小程序源码,专为学校招生场景量身打造,功能实用且操作便捷。 从技术架构来看,ThinkPHP提供稳定可靠的后台服务,FastAdmin加速开发流程,UniApp则保障小程序在多端有良好的兼…...
多模态商品数据接口:融合图像、语音与文字的下一代商品详情体验
一、多模态商品数据接口的技术架构 (一)多模态数据融合引擎 跨模态语义对齐 通过Transformer架构实现图像、语音、文字的语义关联。例如,当用户上传一张“蓝色连衣裙”的图片时,接口可自动提取图像中的颜色(RGB值&…...
MODBUS TCP转CANopen 技术赋能高效协同作业
在现代工业自动化领域,MODBUS TCP和CANopen两种通讯协议因其稳定性和高效性被广泛应用于各种设备和系统中。而随着科技的不断进步,这两种通讯协议也正在被逐步融合,形成了一种新型的通讯方式——开疆智能MODBUS TCP转CANopen网关KJ-TCPC-CANP…...
免费数学几何作图web平台
光锐软件免费数学工具,maths,数学制图,数学作图,几何作图,几何,AR开发,AR教育,增强现实,软件公司,XR,MR,VR,虚拟仿真,虚拟现实,混合现实,教育科技产品,职业模拟培训,高保真VR场景,结构互动课件,元宇宙http://xaglare.c…...
Docker拉取MySQL后数据库连接失败的解决方案
在使用Docker部署MySQL时,拉取并启动容器后,有时可能会遇到数据库连接失败的问题。这种问题可能由多种原因导致,包括配置错误、网络设置问题、权限问题等。本文将分析可能的原因,并提供解决方案。 一、确认MySQL容器的运行状态 …...
ubuntu22.04有线网络无法连接,图标也没了
今天突然无法有线网络无法连接任何设备,并且图标都没了 错误案例 往上一顿搜索,试了很多博客都不行,比如 Ubuntu22.04右上角网络图标消失 最后解决的办法 下载网卡驱动,重新安装 操作步骤 查看自己网卡的型号 lspci | gre…...
ui框架-文件列表展示
ui框架-文件列表展示 介绍 UI框架的文件列表展示组件,可以展示文件夹,支持列表展示和图标展示模式。组件提供了丰富的功能和可配置选项,适用于文件管理、文件上传等场景。 功能特性 支持列表模式和网格模式的切换展示支持文件和文件夹的层…...
在golang中如何将已安装的依赖降级处理,比如:将 go-ansible/v2@v2.2.0 更换为 go-ansible/@v1.1.7
在 Go 项目中降级 go-ansible 从 v2.2.0 到 v1.1.7 具体步骤: 第一步: 修改 go.mod 文件 // 原 v2 版本声明 require github.com/apenella/go-ansible/v2 v2.2.0 替换为: // 改为 v…...
ArcPy扩展模块的使用(3)
管理工程项目 arcpy.mp模块允许用户管理布局、地图、报表、文件夹连接、视图等工程项目。例如,可以更新、修复或替换图层数据源,修改图层的符号系统,甚至自动在线执行共享要托管在组织中的工程项。 以下代码展示了如何更新图层的数据源&…...
