当前位置: 首页 > news >正文

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. 二分查找【数组 二分查找】 题目描述&#xff1a;解题思路一&#xff1a;注意开区间和闭区间背诵版&#xff1a;解题思路三&#xff1a; 题目描述&#xff1a; 给定一个 n 个元素有序的&#xff08;升序&#xff09;整型数组 nums 和一个目标值 target &#xf…...

Rust 性能分析

都说Rust性能好,但是也得代码写得好,猜猜下面两个代码哪个快 . - 力扣&#xff08;LeetCode&#xff09; 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都是广泛使用的项目自动化构建工具&#xff0c;但它们在多个方面存在差异。以下是关于Gradle和Maven的详细对比&#xff1a; 一、构建脚本语言 Maven&#xff1a;使用XML作为构建脚本语言。XML的语法较为繁琐&#xff0c;不够灵活&#xff0c;对于复杂的构建逻辑…...

Seed-TTS语音编辑有多强?对比实测结果让你惊叹!

GLM-4-9B 开源系列模型 前言 就在最近&#xff0c;ByteDance的研究人员最近推出了一系列名为Seed-TTS的大规模自回归文本转语音(TTS)模型,能够合成几乎与人类语音无法区分的高质量语音。那么Seed-TTS的表现究竟有多强呢?让我们一起来感受下Seed-TTS带来的惊喜吧! 介绍Seed-TTS…...

Vue3——实现word,pdf上传之后,预览功能(实测有效)

vue-office/pdf - npm支持多种文件(**docx、excel、pdf**)预览的vue组件库&#xff0c;支持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之【类的生命周期】

首先&#xff0c;请区分Bean的声明周期和类的声明周期。此处讲的是类的声明周期 可以同步观看另一篇文章JVM之【类加载机制】 概述 在Java中数据类型分为基本数据类型和引用数据类型 基本数据类型由虚拟机预先定义&#xff0c;引用数据类型则需要进行类的加载 按照]ava虚拟机…...

分库分表场景下,如何设计与实现一种高效的分布式ID生成策略

在构建大规模分布式系统时&#xff0c;随着数据量的爆炸式增长&#xff0c;单个数据库往往难以承载如此庞大的数据存储与访问需求。这时&#xff0c;分库分表便成为一种有效的解决方案&#xff0c;它通过将数据分散存储在多个数据库或表中&#xff0c;从而提高系统的处理能力和…...

机器人系统ros2-开发学习实践16-RViz 用户指南

RViz 是 ROS&#xff08;Robot Operating System&#xff09;中的一个强大的 3D 可视化工具&#xff0c;用于可视化机器人模型、传感器数据、路径规划等。以下是RViz用户指南&#xff0c;帮助你了解如何使用RViz来进行机器人开发和调试。 启动可视化工具 ros2 run rviz2 rviz2…...

安全测试 之 安全漏洞 CSRF

1. 背景 安全测试是在功能测试的基础上进行的&#xff0c;它验证软件的安全需求&#xff0c;确保产品在遭受恶意攻击时仍能正常运行&#xff0c;并保护用户信息不受侵犯。 2. CSRF 定义 CSRF&#xff08;Cross-Site Request Forgery&#xff09;&#xff0c;中文名为“跨站请…...

交易中的预测和跟随

任何的交易决策&#xff0c;一定是基于某种推理关系的&#xff0c;这种推理关系是基于t时刻之前的状态&#xff0c;得到t时刻之后的结果&#xff0c;我们基于这种推理关系&#xff0c;根据当前的状态&#xff0c;形成了未来结果的某种预期&#xff0c;然后基于这种预期采取相应…...

vs2022专业版永久密钥

vs2022专业版永久密钥&#xff1a; vs2022专业版永久密钥&#xff1a; Visual Studio 2022 Enterprise&#xff1a;VHF9H-NXBBB-638P6-6JHCY-88JWH Visual Studio 2022 Professional&#xff1a;TD244-P4NB7-YQ6XK-Y8MMM-YWV2J...

MongoDB环境搭建

一.下载安装包 Download MongoDB Community Server | MongoDB 二、双击下载完成后的安装包开始安装&#xff0c;除了以下两个部分需要注意操作&#xff0c;其他直接next就行 三.可视化界面安装 下载MongoDB-compass&#xff0c;地址如下 MongoDB Compass Download (GUI) | M…...

数据结构【队列】

队列的的概念 队列是一种特殊的线性表&#xff0c;特殊之处在于它只允许在表的头部进行删除操作&#xff0c;而在表的尾部进行插入操作&#xff0c;和栈一样&#xff0c;队列是一种操作受限制的线性表。进行插入操作的端称为队尾&#xff0c;进行删除操作的端称为队头。队列中…...

微信小程序上架,AI类目审核(AI问答、AI绘画、AI换脸)

小程序对于生成式AI类目的产品上架审核较为严格&#xff0c;这也是近两年新增了几个类目&#xff0c;一旦小程序中涉及生成式AI相关的内容&#xff0c;如果你选择相应类目&#xff0c;但审核被划归为这一类&#xff0c;都需要准备此类目的审核&#xff0c;才能正常上架。 如果…...

Vue3学习记录(第一天)

Vue3学习记录_第一天 背景说明记录Vue3实现响应式前端的反射前端对象的属性赋值Vue3响应式实现过程稿前端移除对象的属性 背景 本次学习主要是看视频学习, 没有跟练, 但是很多知识点感觉又容易忘记. 所以通过笔记的方式输出一下. 说明 估计只能自己看懂, 如果能提供一些其他…...

springboot+vue+mybatis房屋租贷系统+PPT+论文+讲解+售后

本论文系统地描绘了整个网上房屋租赁系统的设计与实现&#xff0c;主要实现的功能有以下几点&#xff1a;管理员&#xff1b;首页、个人中心、房屋类型管理、房屋租赁管理、会员管理、订单信息管理、合同信息管理、退房评价管理、管理员管理&#xff0c;系统管理&#xff0c;前…...

Day30 登录界面设计

​ 本章节,实现了登录界面窗口设计 一.准备登录界面图片素材(透明背景图片) 把准备好的图片放在 Images 文件夹下面,格式分别是 .png和 .icoico 图片,右键属性,生成操作选 内容 png 图片,右键属性,生成操作选 资源 选中 login.png图片鼠标右键,选择属性。生成的操作选…...

VOJ 迷阵突围 题解 次短路径 dijkstra算法

迷阵突围 题目描述 小明陷入了坐标系上的一个迷阵&#xff0c;迷阵上有 n 个点&#xff0c;编号从 1 到 n 。小明在编号为 1 的位置&#xff0c;他想到编号为 n 的位置上。小明当然想尽快到达目的地&#xff0c;但是他觉得最短的路径可能有风险&#xff0c;所以他会选择第二短…...

Oracle SQL详解

Oracle SQL是一种用于管理和操作Oracle数据库的编程语言。以下是一些基本的Oracle SQL语法和建表建用户的详解。 创建用户 在Oracle中&#xff0c;创建用户通常需要具有足够权限的用户&#xff08;通常是具有DBA角色的用户&#xff09;。以下是一个创建用户的例子&#xff1a;…...

产业,到底需要什么大模型?

[ 产业究竟需要怎样的大模型&#xff1f;关于这个问题&#xff0c;本文作者便提出了他的看法&#xff0c;并总结了产业大模型目前阶段的三点落地挑战。一起来看看&#xff0c;或许可以帮助你更好地理解大模型与行业、与产业的融合。 写下这篇的起因&#xff0c;是前不久的一件事…...

【HarmonyOS 5.0】DevEco Testing:鸿蒙应用质量保障的终极武器

——全方位测试解决方案与代码实战 一、工具定位与核心能力 DevEco Testing是HarmonyOS官方推出的​​一体化测试平台​​&#xff0c;覆盖应用全生命周期测试需求&#xff0c;主要提供五大核心能力&#xff1a; ​​测试类型​​​​检测目标​​​​关键指标​​功能体验基…...

人机融合智能 | “人智交互”跨学科新领域

本文系统地提出基于“以人为中心AI(HCAI)”理念的人-人工智能交互(人智交互)这一跨学科新领域及框架,定义人智交互领域的理念、基本理论和关键问题、方法、开发流程和参与团队等,阐述提出人智交互新领域的意义。然后,提出人智交互研究的三种新范式取向以及它们的意义。最后,总结…...

Go语言多线程问题

打印零与奇偶数&#xff08;leetcode 1116&#xff09; 方法1&#xff1a;使用互斥锁和条件变量 package mainimport ("fmt""sync" )type ZeroEvenOdd struct {n intzeroMutex sync.MutexevenMutex sync.MutexoddMutex sync.Mutexcurrent int…...

Web中间件--tomcat学习

Web中间件–tomcat Java虚拟机详解 什么是JAVA虚拟机 Java虚拟机是一个抽象的计算机&#xff0c;它可以执行Java字节码。Java虚拟机是Java平台的一部分&#xff0c;Java平台由Java语言、Java API和Java虚拟机组成。Java虚拟机的主要作用是将Java字节码转换为机器代码&#x…...

【前端异常】JavaScript错误处理:分析 Uncaught (in promise) error

在前端开发中&#xff0c;JavaScript 异常是不可避免的。随着现代前端应用越来越多地使用异步操作&#xff08;如 Promise、async/await 等&#xff09;&#xff0c;开发者常常会遇到 Uncaught (in promise) error 错误。这个错误是由于未正确处理 Promise 的拒绝&#xff08;r…...

Leetcode33( 搜索旋转排序数组)

题目表述 整数数组 nums 按升序排列&#xff0c;数组中的值 互不相同 。 在传递给函数之前&#xff0c;nums 在预先未知的某个下标 k&#xff08;0 < k < nums.length&#xff09;上进行了 旋转&#xff0c;使数组变为 [nums[k], nums[k1], …, nums[n-1], nums[0], nu…...

Python竞赛环境搭建全攻略

Python环境搭建竞赛技术文章大纲 竞赛背景与意义 竞赛的目的与价值Python在竞赛中的应用场景环境搭建对竞赛效率的影响 竞赛环境需求分析 常见竞赛类型&#xff08;算法、数据分析、机器学习等&#xff09;不同竞赛对Python版本及库的要求硬件与操作系统的兼容性问题 Pyth…...

云原生周刊:k0s 成为 CNCF 沙箱项目

开源项目推荐 HAMi HAMi&#xff08;原名 k8s‑vGPU‑scheduler&#xff09;是一款 CNCF Sandbox 级别的开源 K8s 中间件&#xff0c;通过虚拟化 GPU/NPU 等异构设备并支持内存、计算核心时间片隔离及共享调度&#xff0c;为容器提供统一接口&#xff0c;实现细粒度资源配额…...

在鸿蒙HarmonyOS 5中使用DevEco Studio实现指南针功能

指南针功能是许多位置服务应用的基础功能之一。下面我将详细介绍如何在HarmonyOS 5中使用DevEco Studio实现指南针功能。 1. 开发环境准备 确保已安装DevEco Studio 3.1或更高版本确保项目使用的是HarmonyOS 5.0 SDK在项目的module.json5中配置必要的权限 2. 权限配置 在mo…...

python数据结构和算法(1)

数据结构和算法简介 数据结构&#xff1a;存储和组织数据的方式&#xff0c;决定了数据的存储方式和访问方式。 算法&#xff1a;解决问题的思维、步骤和方法。 程序 数据结构 算法 算法 算法的独立性 算法是独立存在的一种解决问题的方法和思想&#xff0c;对于算法而言&a…...