当前位置: 首页 > 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;可以帮助你查看远程仓库中可用的分支和标签&…...

手游刚开服就被攻击怎么办?如何防御DDoS?

开服初期是手游最脆弱的阶段&#xff0c;极易成为DDoS攻击的目标。一旦遭遇攻击&#xff0c;可能导致服务器瘫痪、玩家流失&#xff0c;甚至造成巨大经济损失。本文为开发者提供一套简洁有效的应急与防御方案&#xff0c;帮助快速应对并构建长期防护体系。 一、遭遇攻击的紧急应…...

蓝牙 BLE 扫描面试题大全(2):进阶面试题与实战演练

前文覆盖了 BLE 扫描的基础概念与经典问题蓝牙 BLE 扫描面试题大全(1)&#xff1a;从基础到实战的深度解析-CSDN博客&#xff0c;但实际面试中&#xff0c;企业更关注候选人对复杂场景的应对能力&#xff08;如多设备并发扫描、低功耗与高发现率的平衡&#xff09;和前沿技术的…...

uniapp中使用aixos 报错

问题&#xff1a; 在uniapp中使用aixos&#xff0c;运行后报如下错误&#xff1a; AxiosError: There is no suitable adapter to dispatch the request since : - adapter xhr is not supported by the environment - adapter http is not available in the build 解决方案&…...

学校时钟系统,标准考场时钟系统,AI亮相2025高考,赛思时钟系统为教育公平筑起“精准防线”

2025年#高考 将在近日拉开帷幕&#xff0c;#AI 监考一度冲上热搜。当AI深度融入高考&#xff0c;#时间同步 不再是辅助功能&#xff0c;而是决定AI监考系统成败的“生命线”。 AI亮相2025高考&#xff0c;40种异常行为0.5秒精准识别 2025年高考即将拉开帷幕&#xff0c;江西、…...

技术栈RabbitMq的介绍和使用

目录 1. 什么是消息队列&#xff1f;2. 消息队列的优点3. RabbitMQ 消息队列概述4. RabbitMQ 安装5. Exchange 四种类型5.1 direct 精准匹配5.2 fanout 广播5.3 topic 正则匹配 6. RabbitMQ 队列模式6.1 简单队列模式6.2 工作队列模式6.3 发布/订阅模式6.4 路由模式6.5 主题模式…...

JVM虚拟机:内存结构、垃圾回收、性能优化

1、JVM虚拟机的简介 Java 虚拟机(Java Virtual Machine 简称:JVM)是运行所有 Java 程序的抽象计算机,是 Java 语言的运行环境,实现了 Java 程序的跨平台特性。JVM 屏蔽了与具体操作系统平台相关的信息,使得 Java 程序只需生成在 JVM 上运行的目标代码(字节码),就可以…...

iOS性能调优实战:借助克魔(KeyMob)与常用工具深度洞察App瓶颈

在日常iOS开发过程中&#xff0c;性能问题往往是最令人头疼的一类Bug。尤其是在App上线前的压测阶段或是处理用户反馈的高发期&#xff0c;开发者往往需要面对卡顿、崩溃、能耗异常、日志混乱等一系列问题。这些问题表面上看似偶发&#xff0c;但背后往往隐藏着系统资源调度不当…...

【笔记】WSL 中 Rust 安装与测试完整记录

#工作记录 WSL 中 Rust 安装与测试完整记录 1. 运行环境 系统&#xff1a;Ubuntu 24.04 LTS (WSL2)架构&#xff1a;x86_64 (GNU/Linux)Rust 版本&#xff1a;rustc 1.87.0 (2025-05-09)Cargo 版本&#xff1a;cargo 1.87.0 (2025-05-06) 2. 安装 Rust 2.1 使用 Rust 官方安…...

JavaScript基础-API 和 Web API

在学习JavaScript的过程中&#xff0c;理解API&#xff08;应用程序接口&#xff09;和Web API的概念及其应用是非常重要的。这些工具极大地扩展了JavaScript的功能&#xff0c;使得开发者能够创建出功能丰富、交互性强的Web应用程序。本文将深入探讨JavaScript中的API与Web AP…...

C#中的CLR属性、依赖属性与附加属性

CLR属性的主要特征 封装性&#xff1a; 隐藏字段的实现细节 提供对字段的受控访问 访问控制&#xff1a; 可单独设置get/set访问器的可见性 可创建只读或只写属性 计算属性&#xff1a; 可以在getter中执行计算逻辑 不需要直接对应一个字段 验证逻辑&#xff1a; 可以…...