leetcode 704 二分查找
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]之间。
from typing import Listclass Solution:def search(self, nums: List[int], target: int) -> int:# 初始化左边界和右边界left, right = 0, len(nums) - 1# 当左边界小于等于右边界时,继续搜索while left <= right:# 计算中点索引,避免直接相加导致溢出mid = (right - left) // 2 + leftnum = nums[mid] # 获取中点位置的元素# 检查中点位置的元素是否等于目标值if num == target:return mid # 如果找到了目标值,返回中点索引# 如果中点的元素大于目标值,缩小右边界至中点的左侧elif num > target:right = mid - 1# 如果中点的元素小于目标值,缩小左边界至中点的右侧else:left = mid + 1# 如果循环结束仍未找到目标值,返回 -1return -1
注释解释
-
初始化左右边界:
left设置为数组的起始位置0,right设置为数组的末尾位置len(nums) - 1,表示我们将要在整个数组范围内查找目标值。 -
循环条件:
通过while left <= right控制搜索范围,当left超过right时,说明目标值不存在于数组中,退出循环。 -
计算中点:
mid = (right - left) // 2 + left用于计算当前left和right之间的中点,保证计算不会因直接相加而导致溢出问题。 -
目标值检查:
- 如果找到了目标值
nums[mid] == target,直接返回mid索引,算法结束。 - 如果目标值比中点元素小
num > target,说明目标值在中点左侧,因此将right更新为mid - 1,缩小搜索范围。 - 如果目标值比中点元素大
num < target,说明目标值在中点右侧,因此将left更新为mid + 1。
- 如果找到了目标值
-
返回 -1:
如果循环结束且没有找到目标值,则返回 -1 表示目标值不存在于数组中。
class Solution {public int search(int[] nums, int target) {// 初始化左右边界int left = 0, right = nums.length - 1;// 当左边界小于等于右边界时,继续二分查找while (left <= right) {// 计算中点索引,避免直接相加导致溢出int mid = (right - left) / 2 + left;int num = nums[mid]; // 获取中点位置的元素// 检查中点位置的元素是否等于目标值if (num == target) {return mid; // 如果找到目标值,返回中点索引} // 如果中点元素大于目标值,则缩小搜索范围到左半边else if (num > target) {right = mid - 1;} // 如果中点元素小于目标值,则缩小搜索范围到右半边else {left = mid + 1;}}// 如果循环结束仍未找到目标值,返回 -1return -1;} }
二分查找 为什么mid = right // 2这样不行 需要mid = (right - left) // 2 + left
在二分查找中,
mid的计算需要使用(right + left) // 2或(right - left) // 2 + left,而不是right // 2。这是因为mid = right // 2会导致错误的中点计算,特别是在left不为0的情况下。这里是原因的具体分析:
错误的中点计算:当你直接用
mid = right // 2时,计算出的中点并没有考虑left的偏移量。这会导致在某些情况下,特别是当left不为0时,mid指向数组的错误位置,从而导致算法无法正常工作。正确的中点计算:
mid = (right + left) // 2或mid = (right - left) // 2 + left能够动态计算出当前搜索范围的中点位置,从而确保了二分查找的正确性。
right - left确保了范围的长度。+ left将中点偏移到当前搜索范围的开头,避免忽略left的影响。避免溢出:在某些编程语言中,直接用
(right + left) // 2可能导致溢出(如果right和left都很大),而(right - left) // 2 + left可以规避这一问题(Python中不存在这个问题,因为它的int是动态扩展的)。因此,推荐使用
mid = (right + left) // 2或mid = (right - left) // 2 + left来确保算法的正确性和稳定性。
相关文章:
leetcode 704 二分查找
704. 二分查找 已解答 简单 相关标签 相关企业 给定一个 n 个元素有序的(升序)整型数组 nums 和一个目标值 target ,写一个函数搜索 nums 中的 target,如果目标值存在返回下标,否则返回 -1。 示例 1: 输入: nu…...
Vue学习笔记(十一)
一. Promise 1. 异步 异步:则是将耗时很长的A交付的工作交给系统之后,就去继续做B交付的工作,等到系统完成了前面的工作之后,再通过回调或者事件,继续做A剩下的工作。AB工作的完成顺序,和交付他们的时间顺…...
ABAP进阶学习1:动态内表1-通过系统表LVC_T_FCAT类型定义内表
动态内表1-通过系统表LVC_T_FCAT类型定义内表 如果对你有帮助,点个关注收藏吧~ 做BW做久了,突然对abap有了探索欲,开始进一步学习abap了,以后这个系列会逐步更新,欢迎小伙伴点个关注一起学习,我学习的方法…...
【Vispy库】一个用于高性能交互式2D/3D数据可视化库 Python库
Vispy库 1、你好,Vispy!2、安装Vispy,轻松上手3、案例一:绘制简单的2D图形4、案例二:3D图形的绘制5、案例三:大规模数据的可视化6、结语 1、你好,Vispy! Vispy是一个用于Python的高…...
为什么 C 语言数组是从 0 开始计数的?
C 语言等大多数编程语言的数组从 0 开始而不从 1 开始,有两个原因: 第一:地址计算更方便 C 语言从 0 开始的话,array[i] 的地址就正好是: (array i) 如果是从 1 开始的话,就是 (array i - 1) 多一次计…...
matlab线性度计算程序
matlab线性度计算程序 环境 matlab2023a ads2020 原理 其中f(v)是曲线,fmax是f(v)的最大值,fmin是f(v)的最小值,vmax为fmax对应v值,vmin为fmin对应v值。 L∆fmax/(fmax-fmin) (1) ∆fmaxmax[f(v)-[fmin-K*(v-vmin)]] (2) K(…...
为什么NMOS管比PMOS管更受欢迎?
NMOS在实际应用中为何比PMOS要更受欢迎。本文将从导电沟道、电子迁移率和器件速度等多个方面来展开讲解。 首先是在性能方面考虑: 与NMOS管驱动能力相同的一个PMOS管,其器件面积可能是NMOS管的2~3倍,然而器件面积会影响导通电阻…...
【论文复现】短期电力负荷
作者主页: 七七的个人主页 文章收录专栏: 论文复现 欢迎大家点赞 👍 收藏 ⭐ 加关注哦!💖💖 短期电力负荷 论文发表问题背景一. 基本问题二. 本论文发现的问题 对于论文发现问题的解决方案:复现…...
pytest脚本常用的执行命令
pytest脚本常用的执行命令 一、一般执行的脚本,执行.py文件整个脚本二、执行.py文件脚本中的一个模块三、执行脚本,执行.py文件整个脚本,或则一个模块,查看对应的日志信息3.1.py文件执行allure的脚本3.2去dos框下去执行对应的脚本…...
OpenCv入门
一.OpenCv简介 1 图像的起源 1.1图像是什么? 图:是物体反射或透射光的分布 像:是人的视觉系统所接受的图在人脑中所形版的印象或认识 1.2模拟图像和数字图像 模拟图像:连续存储的图像 数字图像:分级存储的图像 2 数字…...
超详细的flex教程(面试必考)
引言 为什么存在? Flex 布局的出现是为了解决传统 CSS 布局方式(如浮动布局、定位布局等)在处理复杂布局时的诸多限制和不便。 优势 1. 简化布局 Flex 布局的语法简洁明了,代码更易读。 2. 强大的对齐能力 提供丰富的对齐属…...
C++的输入与输出
一.格式和注意要点 1. #include<iostream>; using namespace std; 标准库定义了4个IO对象,IO(输入输出),以下: cin是一个istream流对象,现在理解为标准输入即可。cout是一个ostream流对象,理解为标准输出即可。…...
上海剧某文化传播有限公司与喜某(上海)网络科技有限公司、上海喜某科技有限公司侵害著作权及不正当竞争纠纷案
上海剧某文化传播有限公司与喜某(上海)网络科技有限公司、上海喜某科技有限公司侵害著作权及不正当竞争纠纷案的详细情况如下: 基本案情: 上海剧某文化传播有限公司(以下简称剧某公司)是电视剧《宸汐缘》的…...
【c++篇】:模拟实现string类--探索字符串操作的底层逻辑
✨感谢您阅读本篇文章,文章内容是个人学习笔记的整理,如果哪里有误的话还请您指正噢✨ ✨ 个人主页:余辉zmh–CSDN博客 ✨文章所属专栏:c篇–CSDN博客 文章目录 前言一.string类的默认成员函数以及深拷贝1.基本框架2.默认成员函数…...
springboot配置logback.xml遇到的几个问题
最近项目用到对日志脱敏,经过研究通过logback实现了对日志脱敏,上篇文章中详细讲解了如果配置。但是还是对logback的配置不太了解。比如springboot怎么加载这个logback.xml的。 首先,默认情况下,logback.xml文件是放在类目录下&am…...
MySQL 5.7与MySQL 8.0对比
一、功能对比 JSON支持 MySQL 5.7:引入了JSON数据类型,允许用户存储和操作JSON格式的数据,这是NoSQL功能的一个重要补充。但相对于MySQL 8.0,其功能和性能较弱。MySQL 8.0:在JSON支持方面进行了重大改进,引…...
【代码随想录Day55】图论Part07
prim 算法精讲 题目链接/文章讲解:代码随想录 import java.util.*;public class Main {public static void main(String[] args) {Scanner scanner new Scanner(System.in);// 读取顶点数和边数int vertexCount scanner.nextInt();int edgeCount scanner.nextI…...
软考在即!这些注意事项你提前了解!
11月软考马上就要开始了,但是,还有很多的考生,可能还不知道自己到底应该去了解些什么?本文将详细介绍机考注意事项及系统操作提示,帮助考生们备考无忧。 一、考试入场要求和考场规则 1、入场时间:考生需提…...
CMake知识点
参考: https://zhuanlan.zhihu.com/p/661284252 cmake使用教程(实操版)-CSDN博客 【CMake】CMake从入门到实战系列(二)——实例入手,讲解CMake的基本流程_cmake创建一个可执行目标的过程-CSDN博客 一、…...
git ls-remote
文章目录 1.简介2.格式3.选项4.示例5.小结参考文献 1.简介 git ls-remote 是一个 Git 命令,用于列出远程 Git 仓库的引用(refs),包括分支、标签等。 这个命令非常有用,可以帮助你查看远程仓库中可用的分支和标签&…...
C++初阶-list的底层
目录 1.std::list实现的所有代码 2.list的简单介绍 2.1实现list的类 2.2_list_iterator的实现 2.2.1_list_iterator实现的原因和好处 2.2.2_list_iterator实现 2.3_list_node的实现 2.3.1. 避免递归的模板依赖 2.3.2. 内存布局一致性 2.3.3. 类型安全的替代方案 2.3.…...
【Linux】shell脚本忽略错误继续执行
在 shell 脚本中,可以使用 set -e 命令来设置脚本在遇到错误时退出执行。如果你希望脚本忽略错误并继续执行,可以在脚本开头添加 set e 命令来取消该设置。 举例1 #!/bin/bash# 取消 set -e 的设置 set e# 执行命令,并忽略错误 rm somefile…...
uni-app学习笔记二十二---使用vite.config.js全局导入常用依赖
在前面的练习中,每个页面需要使用ref,onShow等生命周期钩子函数时都需要像下面这样导入 import {onMounted, ref} from "vue" 如果不想每个页面都导入,需要使用node.js命令npm安装unplugin-auto-import npm install unplugin-au…...
YSYX学习记录(八)
C语言,练习0: 先创建一个文件夹,我用的是物理机: 安装build-essential 练习1: 我注释掉了 #include <stdio.h> 出现下面错误 在你的文本编辑器中打开ex1文件,随机修改或删除一部分,之后…...
【Redis技术进阶之路】「原理分析系列开篇」分析客户端和服务端网络诵信交互实现(服务端执行命令请求的过程 - 初始化服务器)
服务端执行命令请求的过程 【专栏简介】【技术大纲】【专栏目标】【目标人群】1. Redis爱好者与社区成员2. 后端开发和系统架构师3. 计算机专业的本科生及研究生 初始化服务器1. 初始化服务器状态结构初始化RedisServer变量 2. 加载相关系统配置和用户配置参数定制化配置参数案…...
pam_env.so模块配置解析
在PAM(Pluggable Authentication Modules)配置中, /etc/pam.d/su 文件相关配置含义如下: 配置解析 auth required pam_env.so1. 字段分解 字段值说明模块类型auth认证类模块,负责验证用户身份&am…...
1688商品列表API与其他数据源的对接思路
将1688商品列表API与其他数据源对接时,需结合业务场景设计数据流转链路,重点关注数据格式兼容性、接口调用频率控制及数据一致性维护。以下是具体对接思路及关键技术点: 一、核心对接场景与目标 商品数据同步 场景:将1688商品信息…...
【算法训练营Day07】字符串part1
文章目录 反转字符串反转字符串II替换数字 反转字符串 题目链接:344. 反转字符串 双指针法,两个指针的元素直接调转即可 class Solution {public void reverseString(char[] s) {int head 0;int end s.length - 1;while(head < end) {char temp …...
从零开始打造 OpenSTLinux 6.6 Yocto 系统(基于STM32CubeMX)(九)
设备树移植 和uboot设备树修改的内容同步到kernel将设备树stm32mp157d-stm32mp157daa1-mx.dts复制到内核源码目录下 源码修改及编译 修改arch/arm/boot/dts/st/Makefile,新增设备树编译 stm32mp157f-ev1-m4-examples.dtb \stm32mp157d-stm32mp157daa1-mx.dtb修改…...
【开发技术】.Net使用FFmpeg视频特定帧上绘制内容
目录 一、目的 二、解决方案 2.1 什么是FFmpeg 2.2 FFmpeg主要功能 2.3 使用Xabe.FFmpeg调用FFmpeg功能 2.4 使用 FFmpeg 的 drawbox 滤镜来绘制 ROI 三、总结 一、目的 当前市场上有很多目标检测智能识别的相关算法,当前调用一个医疗行业的AI识别算法后返回…...
