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

刷题之Leetcode704题(超级详细)

704. 二分查找

力扣题目链接(opens new window)icon-default.png?t=N7T8https://leetcode.cn/problems/binary-search/

给定一个 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]之间。

思路

这道题目的前提是数组为有序数组,同时题目还强调数组中无重复元素,因为一旦有重复元素,使用二分查找法返回的元素下标可能不是唯一的,这些都是使用二分法的前提条件,当大家看到题目描述满足如上条件的时候,可要想一想是不是可以用二分法了。

二分查找涉及的很多的边界条件,逻辑比较简单,但就是写不好。例如到底是 while(left < right) 还是 while(left <= right),到底是right = middle呢,还是要right = middle - 1呢?

大家写二分法经常写乱,主要是因为对区间的定义没有想清楚,区间的定义就是不变量。要在二分查找的过程中,保持不变量,就是在while寻找中每一次边界的处理都要坚持根据区间的定义来操作,这就是循环不变量规则。

写二分法,区间的定义一般为两种,左闭右闭即[left, right],或者左闭右开即[left, right)。

下面我用这两种区间的定义分别讲解两种不同的二分写法。

二分法第一种写法

第一种写法,我们定义 target 是在一个在左闭右闭的区间里,也就是[left, right] (这个很重要非常重要)

区间的定义这就决定了二分法的代码应该如何写,因为定义target在[left, right]区间,所以有如下两点:

  • while (left <= right) 要使用 <= ,因为left == right是有意义的,所以使用 <=
  • if (nums[middle] > target) right 要赋值为 middle - 1,因为当前这个nums[middle]一定不是target,那么接下来要查找的左区间结束下标位置就是 middle - 1

代码如下:(详细注释)

class Solution {public int search(int[] nums, int target) {// 避免当 target 小于nums[0] nums[nums.length - 1]时多次循环运算if (target < nums[0] || target > nums[nums.length - 1]) {return -1;}int left = 0, right = nums.length - 1;while (left <= right) {int mid = left + ((right - left) >> 1);if (nums[mid] == target)return mid;else if (nums[mid] < target)left = mid + 1;else if (nums[mid] > target)right = mid - 1;}return -1;}
}
  • 时间复杂度:O(log n)
  • 空间复杂度:O(1)

二分法第二种写法

如果说定义 target 是在一个在左闭右开的区间里,也就是[left, right) ,那么二分法的边界处理方式则截然不同。

有如下两点:

  • while (left < right),这里使用 < ,因为left == right在区间[left, right)是没有意义的
  • if (nums[middle] > target) right 更新为 middle,因为当前nums[middle]不等于target,去左区间继续寻找,而寻找区间是左闭右开区间,所以right更新为middle,即:下一个查询区间不会去比较nums[middle]

代码如下:(详细注释)

class Solution {public int search(int[] nums, int target) {int left = 0, right = nums.length;while (left < right) {int mid = left + ((right - left) >> 1);if (nums[mid] == target)return mid;else if (nums[mid] < target)left = mid + 1;else if (nums[mid] > target)right = mid;}return -1;}
}
  • 时间复杂度:O(log n)
  • 空间复杂度:O(1)

总结

二分法是非常重要的基础算法,为什么很多同学对于二分法都是一看就会,一写就废

其实主要就是对区间的定义没有理解清楚,在循环中没有始终坚持根据查找区间的定义来做边界处理。

区间的定义就是不变量,那么在循环中坚持根据查找区间的定义来做边界处理,就是循环不变量规则。

本篇根据两种常见的区间定义,给出了两种二分法的写法,每一个边界为什么这么处理,都根据区间的定义做了详细介绍。

相信看完本篇应该对二分法有更深刻的理解了。

相关题目推荐

        . - 力扣(LeetCode). - 备战技术面试?力扣提供海量技术面试资源,帮助你高效提升编程技能,轻松拿下世界 IT 名企 Dream Offer。icon-default.png?t=N7T8https://leetcode.cn/problems/search-insert-position/description/

  • . - 力扣(LeetCode). - 备战技术面试?力扣提供海量技术面试资源,帮助你高效提升编程技能,轻松拿下世界 IT 名企 Dream Offer。icon-default.png?t=N7T8https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/description/
  • 69.x 的平方根(opens new window)icon-default.png?t=N7T8https://leetcode.cn/problems/sqrtx/
  • 367.有效的完全平方数(opens new window)icon-default.png?t=N7T8https://leetcode.cn/problems/valid-perfect-square/

相关文章:

刷题之Leetcode704题(超级详细)

704. 二分查找 力扣题目链接(opens new window)https://leetcode.cn/problems/binary-search/ 给定一个 n 个元素有序的&#xff08;升序&#xff09;整型数组 nums 和一个目标值 target &#xff0c;写一个函数搜索 nums 中的 target&#xff0c;如果目标值存在返回下标&am…...

leetcode热题100.前k个高频元素

作者&#xff1a;晓宜 &#x1f308;&#x1f308;&#x1f308; 个人简介&#xff1a;互联网大厂Java准入职&#xff0c;阿里云专家博主&#xff0c;csdn后端优质创作者&#xff0c;算法爱好者 ❤️❤️❤️ 你的关注是我前进的动力&#x1f60a; Problem: 347. 前 K 个高频元…...

LangChain Demo | Agent X ReAct X wikipedia 询问《三体》的主要内容

背景 LangChain学习中&#xff0c;尝试改了一下哈里森和吴恩达课程当中的问题&#xff0c;看看gpt-3.5-turbo在集成了ReAct和wikipedia后&#xff0c;如何回答《三体》的主要内容是什么这个问题&#xff0c;当然&#xff0c;主要是为了回答这问题时LangChain内部发生了什么。所…...

Revit 2025新功能一览~

Hello大家好&#xff01;我是九哥~ Revit2025已经更新&#xff0c;安装后&#xff0c;简单试了下&#xff0c;还是挺不错的&#xff0c;流畅度啊&#xff0c;新功能啊&#xff0c;看来还是有听取用户意见的&#xff0c;接下来就简单看看都有哪些新功能。 好了&#xff0c;今天的…...

Head First Design Patterns -代理模式

什么是代理模式 代理模式为另一个对象提供替身或者占位符&#xff0c;以便控制客户对对象的访问&#xff0c;管理访问的方式有很多种。例如远程代理、虚拟代理、保护代理等。 远程代理&#xff1a;管理客户和远程对象之间的交互。 虚拟代理&#xff1a;控制访问实例化开销大的对…...

第十三题:天干地支

题目描述 古代中国使用天干地支来记录当前的年份。 天干一共有十个&#xff0c;分别为&#xff1a;甲&#xff08;jiǎ&#xff09;、乙&#xff08;yǐ&#xff09;、丙&#xff08;bǐng&#xff09;、丁&#xff08;dīng&#xff09;、戊&#xff08;w&#xff09;、己&a…...

8000预算可以购买阿里云服务器配置整理

一个月8000元预算如何选择阿里云服务器配置&#xff1f;八千预算可选的阿里云服务器配置相当高了&#xff0c;这个预算可以购买阿里云企业级独享型云服务器&#xff0c;至少8核以上的配置&#xff0c;这个预算可以支持复杂、高负载或大规模的业务需求。阿里云服务器网整理8000元…...

游戏APP如何提高广告变现收益的同时,保证用户留存率?

APP广告变现对接第三方聚合广告平台主要通过SDK文档对接&#xff0c;一些媒体APP不具备专业运营广告变现的对接能力和资源沉淀&#xff0c;导致APP被封控&#xff0c;设置列入黑名单&#xff0c;借助第三方聚合广告平台进行商业化变现是最佳选择。#APP广告变现# 接入第三方平台…...

Linux ulimit命令教程:如何查看和设置系统资源限制(附实例详解和注意事项)

Linux ulimit命令介绍 ulimit是一个内置的Linux shell命令&#xff0c;它允许查看或限制单个用户可以消耗的系统资源量。在有多个用户和系统性能问题的环境中&#xff0c;限制资源使用是非常有价值的。 Linux ulimit命令适用的Linux版本 ulimit命令在所有主流的Linux发行版中…...

(delphi11最新学习资料) Object Pascal 学习笔记---第8章第5节(封闭类和Final方法)

8.5.2 封闭类和Final方法 如前所述&#xff0c;Java 采用非常动态的方法&#xff0c;默认情况下采用延迟绑定&#xff08;或虚函数&#xff09;。因此&#xff0c;Java 语言引入了一些概念&#xff0c;如不能继承的类&#xff08;封闭类&#xff09;和不能在派生类中覆盖的方法…...

vue3从精通到入门12:vue3的生命周期和组件

生命周期&#xff1a; 生命周期钩子主要包括&#xff1a; beforeCreate&#xff1a;组件实例被创建之前调用。在这个阶段&#xff0c;组件的 props 和 data 还未被初始化。created&#xff1a;组件实例创建完成后调用。在这个阶段&#xff0c;组件的 props 和 data 已经被初始…...

力扣热题100_链表_21_合并两个有序链表

文章目录 题目链接解题思路解题代码 题目链接 21. 合并两个有序链表 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 示例 1&#xff1a; 输入&#xff1a;l1 [1,2,4], l2 [1,3,4] 输出&#xff1a;[1,1,2,3,4,4] 示例…...

探索未来智慧酒店网项目接口架构

在数字化时代&#xff0c;智慧酒店已成为酒店业发展的重要趋势之一。智慧酒店网项目接口架构作为支撑智慧酒店运营的核心技术之一&#xff0c;其设计和优化对于提升用户体验、提高管理效率具有重要意义。本文将深入探讨智慧酒店网项目接口架构的设计理念和关键要素。 ### 智慧…...

os模块篇(十三)

文章目录 os.mknod(path, mode0o600, device0, *, dir_fdNone)os.major(device, /)os.minor(device, /)os.makedev(major, minor, /)os.pathconf(path, name)os.readlink(path, *, dir_fdNone)os.remove(path, *, dir_fdNone)os.removedirs(name)os.rename(src, dst, *, src_di…...

【JavaEE初阶系列】——文件操作 IO 之 文件系统操作

目录 &#x1f4dd;认识文件 &#x1f6a9;树型结构组织 和 目录 &#x1f388;绝对路径和相对路径 &#x1f6a9;文件类型 &#x1f4dd;文件系统操作 &#x1f388;File 概述 &#x1f388;File类的使用 1. 绝对路径 vs 相对路径 2. 路径分隔符 3. 静态成员变量 4…...

JAVA 学习·类与方法

不同于 C &#xff0c;Java 是一门面向对象的编程语言。C 也有面向对象的内容&#xff0c;但是 C 和 Java 在方法的具体实现上存在区别。 方法的定义 方法(method)是为执行一个复杂操作组合在一起的语句集合。一个类中可以声明多个方法。其语法是采用 BNF 范式&#xff08;Bac…...

4. python练习题4-水仙花数

4. python练习题4-水仙花数 【目录】 文章目录 4. python练习题4-水仙花数1. 目标任务2. 水仙花数的特点3. 如何判断一个数是否是水仙花数&#xff1f;4. 打印3位水仙花数5. 判断一个数是不是水仙花数6. 列表推导式6. 列表推导式判断一个数是不是水仙花数 【正文】 1. 目标任务…...

【Qt 学习笔记】Qt 开发环境的搭建 | Qt 安装教程

博客主页&#xff1a;Duck Bro 博客主页系列专栏&#xff1a;Qt 专栏关注博主&#xff0c;后期持续更新系列文章如果有错误感谢请大家批评指出&#xff0c;及时修改感谢大家点赞&#x1f44d;收藏⭐评论✍ Qt 开发环境的搭建 | Qt 安装教程 文章编号&#xff1a;Qt 学习笔记 /…...

ids工业相机与电控位移台同步控制及数据采集

通过VS2017和OpenCV,实现ids工业相机与电控位移台同步控制及数据采集 目录项目环境配置代码流程及思路项目架构项目开发运行效果开发关键ids相机配置位移台环境配置相机头文件相机参数设置保存图像函数设置电控位移台头文件电控位移台设置参数最后就是通过main函数进行调用和控…...

景联文科技提供高质量医疗健康AI大模型数据

医疗行业是典型的知识和技术密集型行业&#xff0c;其发展水平直接关系到国民健康和生命质量。 医疗健康AI大模型&#xff0c;作为人工智能的一个分支&#xff0c;能够通过学习大量的数据来生成新的数据实例&#xff0c;在医药研发、医学影像、医疗文本分析等都有广泛的应用前景…...

【Python第三方库】lxml 解析器和xpath路径语言

1.lxml是做什么的 是xml/html的解析器&#xff0c;主要是用来解析和提取html/xml数据 2.lxml语法 使用etree.HTML(html字符串)&#xff0c;将字符串转换为Element对象通过使用Element对象.xpath(语法)提取信息,返回的是一个列表的内存地址&#xff0c;需要通过使用索引获取信…...

Java(Lambda、集合)、题解

一、Lambda表达式 标准格式 &#xff08;&#xff09;对应方法的形参 &#xff1b;->固定格式 注意点&#xff1a; Lambda表达式可以用来简化匿名内部类的书写 Lambda表达式只能简化函数式接口的匿名内部类的写法 函数式接口: 有且仅有一个抽象方法的接口叫做函数式接口&…...

Transformer学习: Transformer小模块学习--位置编码,多头自注意力,掩码矩阵

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 Transformer学习 1 位置编码模块1.1 PE代码1.2 测试PE1.3 原文代码 2 多头自注意力模块2.1 多头自注意力代码2.2 测试多头注意力 3 未来序列掩码矩阵3.1 代码3.2 测试掩码 1 …...

easyexcel 动态列导出

1. 引入easyexcel <dependency><groupId>com.alibaba</groupId><artifactId>easyexcel</artifactId><version>3.2.1</version></dependency> 2.导出write public void export(HttpServletResponse response) {try {String f…...

flink源码编译-job提交

1、启动standalone集群的taskmanager standalone集群中的taskmanager启动类为 TaskManagerRunner 2 打开master启动类 通过 ctrln快捷键&#xff0c;找到、并打开类&#xff1a; org.apache.flink.runtime.taskexecutor.TaskManagerRunner 3 修改运⾏配置 基本完全按照mas…...

Mysql密码修改问题

docker安装mysql&#xff0c;直接拉取镜像&#xff0c;挂载关键目录即可启动&#xff0c;默认3306端口。此时无法直接连接&#xff0c;需要配置密码。docker进入mysql容器中 docker exec -it mysql bash #mysq是容器名称&#xff0c;也可以用容器id通过修改mysql的配置进行免密…...

建独立站,对FP商家有什么好处?

2024年都过去四分之一了&#xff0c;还有许多人对是否投身于跨境独立站领域仍犹豫不决。然而&#xff0c;观望不如实践&#xff0c;如果渴望在跨境电商领域开创一片新天地&#xff0c;那么现在就是行动的最佳时机。 特别是对于FP商家来说&#xff0c;由于电商平台对于黑五类产品…...

使用Postman进行websocket接口测试

因为最近要搞关于基于AI的文本接口测试.需要用到websocket协议,于是看了一下发现postman也可以测而且很方便 位置 File->New->WebSocket 可以看到不止WebSocket还支持其他的各种协议 使用 首先先点击connect进行连接 连接成功之后可以选择多种文本格式添加请求参数 每…...

Android音视频开发 - MediaMetadataRetriever 相关

Android音视频开发 - MediaMetadataRetriever 相关 MediaMetadataRetriever 是android中用于从媒体文件中提取元数据新的类. 可以获取音频,视频和图像文件的各种信息,如时长,标题,封面等. 1:初始化对象 private MediaMetadataRetriever mediaMetadataRetriever new MediaMe…...

注解(Annotation)

10.1 注解概述 10.1.1 什么是注解 注解&#xff08;Annotation&#xff09;是从JDK5.0开始引入&#xff0c;以“注解名”在代码中存在。例如&#xff1a; Override Deprecated SuppressWarnings(value”unchecked”) Annotation 可以像修饰符一样被使用&#xff0c;可用于修饰…...

网站 被攻击_主业篡改 被黑了 织梦做的站/晋江友情链接是什么意思

本文无意选择或推荐阵营&#xff0c;毕竟单片机大同小异&#xff0c;基于各自不同的知识水平和预算以及团队选择&#xff0c;谈不上对错&#xff0c;只是从菜鸟到老鸟的路径曲折程度不同而已。 年前收到“STC开天斧”开发板&#xff08;这波免费包邮送的力度很大&#xff09;&a…...

上海做兼职网站有吗/公众号seo排名软件

本工具用于快速求出通信中CRC16校验值&#xff0c;包括&#xff1a;1)CRC-16/DECT-R(别名&#xff1a;R-CRC-16)、2)CRC-16/DECT-X(别名&#xff1a;X-CRC-16)、3)CRC-16/GENIBUS(别名&#xff1a;CRC-16/EPC, CRC-16/I-CODE, CRC-16/DARC)、4)CRC-16/TMS37157、5)CRC-16/RIELL…...

网站建设预付款/网址怎么创建

1 LSA Introduction LSA(latent semantic analysis)潜在语义分析&#xff0c;也被称为LSI(latent semantic index)&#xff0c;是Scott Deerwester, Susan T. Dumais等人在1990年提出来的一种新的索引和检索方法。该方法和传统向量空间模型(vector space model)一样使用向量来表…...

app制作教程步骤和方法/seo知识是什么意思

文章目录1.核心组件2.分析各个组件的源码3.组件之间的关系分析4.组件的共同部分1.核心组件 Tomcat核心组件的架构层次 一个Catalina的请求过程 Server相当于整个服务器, 实现类为StandardServerServer中有Listner, GlobalNamingResources, Service一个Service服务中有很多Conne…...

网站关键词可以做几个/企业邮箱哪个好

点击上方“蓝色字”可关注我们&#xff01;暴走时评&#xff1a;日本交易所集团最近发布超级账本研究报告&#xff0c;对比目前主要的几种DLT方案&#xff0c;阐述该技术如何提高交易效率&#xff0c;以及该技术在金融服务中的可行性。作者提到秘密资产交易可能带来中心化和交易…...

建工网论坛/seo基础课程

测试机器学习算法 现在你对机器学习算法的分类已经有了一个大体的了解&#xff0c;但在更进一步了解每个算法的细节之前&#xff0c;你还需要对如何测试机器学习算法有一个大体的认识。 在大多数情况下&#xff0c;将会出现以下三类数据&#xff1a;训练数据集&#xff08;trai…...