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

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

提示:

  1. 你可以假设 nums 中的所有元素是不重复的。
  2. n 将在 [1, 10000]之间。
  3. 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

注释解释

  1. 初始化左右边界:
    left 设置为数组的起始位置 0right 设置为数组的末尾位置 len(nums) - 1,表示我们将要在整个数组范围内查找目标值。

  2. 循环条件:
    通过 while left <= right 控制搜索范围,当 left 超过 right 时,说明目标值不存在于数组中,退出循环。

  3. 计算中点:
    mid = (right - left) // 2 + left 用于计算当前 leftright 之间的中点,保证计算不会因直接相加而导致溢出问题。

  4. 目标值检查:

    • 如果找到了目标值 nums[mid] == target,直接返回 mid 索引,算法结束。
    • 如果目标值比中点元素小 num > target,说明目标值在中点左侧,因此将 right 更新为 mid - 1,缩小搜索范围。
    • 如果目标值比中点元素大 num < target,说明目标值在中点右侧,因此将 left 更新为 mid + 1
  5. 返回 -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的情况下。这里是原因的具体分析:

  1. 错误的中点计算:当你直接用mid = right // 2时,计算出的中点并没有考虑left的偏移量。这会导致在某些情况下,特别是当left不为0时,mid指向数组的错误位置,从而导致算法无法正常工作。

  2. 正确的中点计算mid = (right + left) // 2mid = (right - left) // 2 + left能够动态计算出当前搜索范围的中点位置,从而确保了二分查找的正确性。

    • right - left确保了范围的长度。
    • + left将中点偏移到当前搜索范围的开头,避免忽略left的影响。
  3. 避免溢出:在某些编程语言中,直接用(right + left) // 2可能导致溢出(如果rightleft都很大),而(right - left) // 2 + left可以规避这一问题(Python中不存在这个问题,因为它的int是动态扩展的)。

因此,推荐使用 mid = (right + left) // 2mid = (right - left) // 2 + left 来确保算法的正确性和稳定性。

相关文章:

leetcode 704 二分查找

704. 二分查找 已解答 简单 相关标签 相关企业 给定一个 n 个元素有序的&#xff08;升序&#xff09;整型数组 nums 和一个目标值 target &#xff0c;写一个函数搜索 nums 中的 target&#xff0c;如果目标值存在返回下标&#xff0c;否则返回 -1。 示例 1: 输入: nu…...

Vue学习笔记(十一)

一. Promise 1. 异步 异步&#xff1a;则是将耗时很长的A交付的工作交给系统之后&#xff0c;就去继续做B交付的工作&#xff0c;等到系统完成了前面的工作之后&#xff0c;再通过回调或者事件&#xff0c;继续做A剩下的工作。AB工作的完成顺序&#xff0c;和交付他们的时间顺…...

ABAP进阶学习1:动态内表1-通过系统表LVC_T_FCAT类型定义内表

动态内表1-通过系统表LVC_T_FCAT类型定义内表 如果对你有帮助&#xff0c;点个关注收藏吧~ 做BW做久了&#xff0c;突然对abap有了探索欲&#xff0c;开始进一步学习abap了&#xff0c;以后这个系列会逐步更新&#xff0c;欢迎小伙伴点个关注一起学习&#xff0c;我学习的方法…...

【Vispy库】一个用于高性能交互式2D/3D数据可视化库 Python库

Vispy库 1、你好&#xff0c;Vispy&#xff01;2、安装Vispy&#xff0c;轻松上手3、案例一&#xff1a;绘制简单的2D图形4、案例二&#xff1a;3D图形的绘制5、案例三&#xff1a;大规模数据的可视化6、结语 1、你好&#xff0c;Vispy&#xff01; Vispy是一个用于Python的高…...

为什么 C 语言数组是从 0 开始计数的?

C 语言等大多数编程语言的数组从 0 开始而不从 1 开始&#xff0c;有两个原因&#xff1a; 第一&#xff1a;地址计算更方便 C 语言从 0 开始的话&#xff0c;array[i] 的地址就正好是&#xff1a; (array i) 如果是从 1 开始的话&#xff0c;就是 (array i - 1) 多一次计…...

matlab线性度计算程序

matlab线性度计算程序 环境 matlab2023a ads2020 原理 其中f(v)是曲线&#xff0c;fmax是f(v)的最大值&#xff0c;fmin是f(v)的最小值&#xff0c;vmax为fmax对应v值&#xff0c;vmin为fmin对应v值。 L∆fmax/(fmax-fmin) (1) ∆fmaxmax⁡[f(v)-[fmin-K*(v-vmin)]] (2) K(…...

为什么NMOS管比PMOS管更受欢迎?

NMOS在实际应用中为何比PMOS要更受欢迎。本文将从导电沟道、电子迁移率和器件速度等多个方面来展开讲解。 首先是在性能方面考虑&#xff1a; 与NMOS管驱动能力相同的一个PMOS管&#xff0c;其器件面积可能是NMOS管的2&#xff5e;3倍&#xff0c;然而器件面积会影响导通电阻…...

【论文复现】短期电力负荷

作者主页&#xff1a; 七七的个人主页 文章收录专栏&#xff1a; 论文复现 欢迎大家点赞 &#x1f44d; 收藏 ⭐ 加关注哦&#xff01;&#x1f496;&#x1f496; 短期电力负荷 论文发表问题背景一. 基本问题二. 本论文发现的问题 对于论文发现问题的解决方案&#xff1a;复现…...

pytest脚本常用的执行命令

pytest脚本常用的执行命令 一、一般执行的脚本&#xff0c;执行.py文件整个脚本二、执行.py文件脚本中的一个模块三、执行脚本&#xff0c;执行.py文件整个脚本&#xff0c;或则一个模块&#xff0c;查看对应的日志信息3.1.py文件执行allure的脚本3.2去dos框下去执行对应的脚本…...

OpenCv入门

一.OpenCv简介 1 图像的起源 1.1图像是什么&#xff1f; 图&#xff1a;是物体反射或透射光的分布 像&#xff1a;是人的视觉系统所接受的图在人脑中所形版的印象或认识 1.2模拟图像和数字图像 模拟图像&#xff1a;连续存储的图像 数字图像&#xff1a;分级存储的图像 2 数字…...

超详细的flex教程(面试必考)

引言 为什么存在&#xff1f; Flex 布局的出现是为了解决传统 CSS 布局方式&#xff08;如浮动布局、定位布局等&#xff09;在处理复杂布局时的诸多限制和不便。 优势 1. 简化布局 Flex 布局的语法简洁明了&#xff0c;代码更易读。 2. 强大的对齐能力 提供丰富的对齐属…...

C++的输入与输出

一.格式和注意要点 1. #include<iostream>; using namespace std; 标准库定义了4个IO对象&#xff0c;IO(输入输出)&#xff0c;以下&#xff1a; cin是一个istream流对象&#xff0c;现在理解为标准输入即可。cout是一个ostream流对象&#xff0c;理解为标准输出即可。…...

上海剧某文化传播有限公司与喜某(上海)网络科技有限公司、上海喜某科技有限公司侵害著作权及不正当竞争纠纷案

上海剧某文化传播有限公司与喜某&#xff08;上海&#xff09;网络科技有限公司、上海喜某科技有限公司侵害著作权及不正当竞争纠纷案的详细情况如下&#xff1a; 基本案情&#xff1a; 上海剧某文化传播有限公司&#xff08;以下简称剧某公司&#xff09;是电视剧《宸汐缘》的…...

【c++篇】:模拟实现string类--探索字符串操作的底层逻辑

✨感谢您阅读本篇文章&#xff0c;文章内容是个人学习笔记的整理&#xff0c;如果哪里有误的话还请您指正噢✨ ✨ 个人主页&#xff1a;余辉zmh–CSDN博客 ✨文章所属专栏&#xff1a;c篇–CSDN博客 文章目录 前言一.string类的默认成员函数以及深拷贝1.基本框架2.默认成员函数…...

springboot配置logback.xml遇到的几个问题

最近项目用到对日志脱敏&#xff0c;经过研究通过logback实现了对日志脱敏&#xff0c;上篇文章中详细讲解了如果配置。但是还是对logback的配置不太了解。比如springboot怎么加载这个logback.xml的。 首先&#xff0c;默认情况下&#xff0c;logback.xml文件是放在类目录下&am…...

MySQL 5.7与MySQL 8.0对比

一、功能对比 JSON支持 MySQL 5.7&#xff1a;引入了JSON数据类型&#xff0c;允许用户存储和操作JSON格式的数据&#xff0c;这是NoSQL功能的一个重要补充。但相对于MySQL 8.0&#xff0c;其功能和性能较弱。MySQL 8.0&#xff1a;在JSON支持方面进行了重大改进&#xff0c;引…...

【代码随想录Day55】图论Part07

prim 算法精讲 题目链接/文章讲解&#xff1a;代码随想录 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月软考马上就要开始了&#xff0c;但是&#xff0c;还有很多的考生&#xff0c;可能还不知道自己到底应该去了解些什么&#xff1f;本文将详细介绍机考注意事项及系统操作提示&#xff0c;帮助考生们备考无忧。 一、考试入场要求和考场规则 1、入场时间&#xff1a;考生需提…...

CMake知识点

参考&#xff1a; https://zhuanlan.zhihu.com/p/661284252 cmake使用教程&#xff08;实操版&#xff09;-CSDN博客 【CMake】CMake从入门到实战系列&#xff08;二&#xff09;——实例入手&#xff0c;讲解CMake的基本流程_cmake创建一个可执行目标的过程-CSDN博客 一、…...

git ls-remote

文章目录 1.简介2.格式3.选项4.示例5.小结参考文献 1.简介 git ls-remote 是一个 Git 命令&#xff0c;用于列出远程 Git 仓库的引用&#xff08;refs&#xff09;&#xff0c;包括分支、标签等。 这个命令非常有用&#xff0c;可以帮助你查看远程仓库中可用的分支和标签&…...

基于FPGA的PID算法学习———实现PID比例控制算法

基于FPGA的PID算法学习 前言一、PID算法分析二、PID仿真分析1. PID代码2.PI代码3.P代码4.顶层5.测试文件6.仿真波形 总结 前言 学习内容&#xff1a;参考网站&#xff1a; PID算法控制 PID即&#xff1a;Proportional&#xff08;比例&#xff09;、Integral&#xff08;积分&…...

边缘计算医疗风险自查APP开发方案

核心目标:在便携设备(智能手表/家用检测仪)部署轻量化疾病预测模型,实现低延迟、隐私安全的实时健康风险评估。 一、技术架构设计 #mermaid-svg-iuNaeeLK2YoFKfao {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg…...

理解 MCP 工作流:使用 Ollama 和 LangChain 构建本地 MCP 客户端

&#x1f31f; 什么是 MCP&#xff1f; 模型控制协议 (MCP) 是一种创新的协议&#xff0c;旨在无缝连接 AI 模型与应用程序。 MCP 是一个开源协议&#xff0c;它标准化了我们的 LLM 应用程序连接所需工具和数据源并与之协作的方式。 可以把它想象成你的 AI 模型 和想要使用它…...

【网络安全产品大调研系列】2. 体验漏洞扫描

前言 2023 年漏洞扫描服务市场规模预计为 3.06&#xff08;十亿美元&#xff09;。漏洞扫描服务市场行业预计将从 2024 年的 3.48&#xff08;十亿美元&#xff09;增长到 2032 年的 9.54&#xff08;十亿美元&#xff09;。预测期内漏洞扫描服务市场 CAGR&#xff08;增长率&…...

【解密LSTM、GRU如何解决传统RNN梯度消失问题】

解密LSTM与GRU&#xff1a;如何让RNN变得更聪明&#xff1f; 在深度学习的世界里&#xff0c;循环神经网络&#xff08;RNN&#xff09;以其卓越的序列数据处理能力广泛应用于自然语言处理、时间序列预测等领域。然而&#xff0c;传统RNN存在的一个严重问题——梯度消失&#…...

土地利用/土地覆盖遥感解译与基于CLUE模型未来变化情景预测;从基础到高级,涵盖ArcGIS数据处理、ENVI遥感解译与CLUE模型情景模拟等

&#x1f50d; 土地利用/土地覆盖数据是生态、环境和气象等诸多领域模型的关键输入参数。通过遥感影像解译技术&#xff0c;可以精准获取历史或当前任何一个区域的土地利用/土地覆盖情况。这些数据不仅能够用于评估区域生态环境的变化趋势&#xff0c;还能有效评价重大生态工程…...

深度学习习题2

1.如果增加神经网络的宽度&#xff0c;精确度会增加到一个特定阈值后&#xff0c;便开始降低。造成这一现象的可能原因是什么&#xff1f; A、即使增加卷积核的数量&#xff0c;只有少部分的核会被用作预测 B、当卷积核数量增加时&#xff0c;神经网络的预测能力会降低 C、当卷…...

LeetCode - 199. 二叉树的右视图

题目 199. 二叉树的右视图 - 力扣&#xff08;LeetCode&#xff09; 思路 右视图是指从树的右侧看&#xff0c;对于每一层&#xff0c;只能看到该层最右边的节点。实现思路是&#xff1a; 使用深度优先搜索(DFS)按照"根-右-左"的顺序遍历树记录每个节点的深度对于…...

GruntJS-前端自动化任务运行器从入门到实战

Grunt 完全指南&#xff1a;从入门到实战 一、Grunt 是什么&#xff1f; Grunt是一个基于 Node.js 的前端自动化任务运行器&#xff0c;主要用于自动化执行项目开发中重复性高的任务&#xff0c;例如文件压缩、代码编译、语法检查、单元测试、文件合并等。通过配置简洁的任务…...

给网站添加live2d看板娘

给网站添加live2d看板娘 参考文献&#xff1a; stevenjoezhang/live2d-widget: 把萌萌哒的看板娘抱回家 (ノ≧∇≦)ノ | Live2D widget for web platformEikanya/Live2d-model: Live2d model collectionzenghongtu/live2d-model-assets 前言 网站环境如下&#xff0c;文章也主…...