Leetcode 搜索旋转排序数组
这段代码是用于解决LeetCode第33题“搜索旋转排序数组”的Java解法。以下是对该算法思想的中文解释:
算法思想
-
二分查找的基本思路:
- 由于数组是部分有序的(被旋转过),我们可以利用二分查找的思想,逐步缩小搜索范围。
- 但是与普通的二分查找不同,这里的数组被旋转过,所以需要先判断当前数组的哪个部分是有序的,再决定如何更新搜索范围。
-
判断有序区间:
- 通过比较
nums[left]
和nums[mid]
,我们可以确定左半部分或右半部分是否是有序的。 - 如果
nums[left] <= nums[mid]
,说明左半部分是有序的。 - 如果
nums[left] > nums[mid]
,说明右半部分是有序的。
- 通过比较
-
确定目标值在哪个区间:
- 如果左半部分是有序的,且目标值
target
在nums[left]
和nums[mid]
之间(即nums[left] <= target < nums[mid]
),那么我们将搜索范围缩小到左半部分,即更新right = mid - 1
。 - 如果目标值不在左半部分,那么我们将搜索范围缩小到右半部分,即更新
left = mid + 1
。 - 同理,如果右半部分是有序的,且目标值
target
在nums[mid]
和nums[right]
之间(即nums[mid] < target <= nums[right]
),则搜索范围缩小到右半部分。 - 否则,目标值在左半部分,因此更新
right = mid - 1
。
- 如果左半部分是有序的,且目标值
-
返回结果:
- 如果找到目标值,则返回它的索引。
- 如果循环结束后仍未找到目标值,则返回
-1
。
Java 代码的逐行解释
class Solution {public int search(int[] nums, int target) {int left = 0;int right = nums.length - 1;while (left <= right) {int mid = left + (right - left) / 2;// 检查中间元素是否为目标值if (nums[mid] == target) {return mid;}// 判断左半部分是否有序if (nums[left] <= nums[mid]) {// 检查目标值是否在左半部分if (nums[left] <= target && target < nums[mid]) {right = mid - 1;} else {left = mid + 1;}}// 右半部分是有序的else {// 检查目标值是否在右半部分if (nums[mid] < target && target <= nums[right]) {left = mid + 1;} else {right = mid - 1;}}}// 未找到目标值,返回-1return -1;}
}
时间复杂度
由于每次循环都会将搜索区间缩小一半,所以时间复杂度为 (O(\log n)),符合题目要求的高效查找。
总结
这个算法巧妙地利用了数组的部分有序特性,结合二分查找,在旋转数组中高效地查找目标值。
为什么如果nums[left] > nums[mid],说明右半部分是有序的。
如果nums[left] > nums[mid],说明左半区间存在旋转断点,而旋转断点之后的子数组都是有序的,所以右半部分是有序的。
当nums[left] > nums[mid]
时,确实可以判断左半区间存在旋转断点,这意味着左半部分并不是完全有序的。而旋转断点之后的子数组会保持有序状态,因此我们可以推断出右半部分是有序的。
这也是为什么在这种情况下,我们可以安全地在右半部分进行查找,前提是目标值target
在右半部分的范围内。反之,如果目标值不在右半部分的范围内,那么就去左半部分继续搜索。
你的理解完全正确!这种判断旋转数组中有序部分的方法,是解决这类问题的关键。😊
为什么这一部分代码片段if (nums[mid] < target && target <= nums[right])
,如果使用判断条件if (nums[mid] <= target && target < nums[right])
会得到错误的答案?
这个问题的核心在于边界条件的不同处理导致的结果差异。让我们仔细分析一下这两个条件的区别,以及为什么会得到不同的答案。
代码片段解释
if (nums[mid] < target && target <= nums[right])
条件比较
- 原条件:
if (nums[mid] < target && target <= nums[right])
- 错误条件:
if (nums[mid] <= target && target < nums[right])
原条件的含义:if (nums[mid] < target && target <= nums[right])
这个条件的意思是:
nums[mid] < target
:目标值target
要比nums[mid]
大。target <= nums[right]
:目标值target
小于或等于nums[right]
。
该条件涵盖了目标值在右半部分有序区间内的情况,包括target
等于nums[right]
的情况。例如,如果右半部分的元素是[1, 2, 3, 4, 5]
,而target = 5
,这个条件会成功匹配到5
。
错误条件的含义:if (nums[mid] <= target && target < nums[right])
这个条件的意思是:
nums[mid] <= target
:目标值target
可以等于nums[mid]
。target < nums[right]
:目标值target
必须严格小于nums[right]
。
这个条件的一个问题是,当目标值等于nums[right]
时,不会满足条件,即使target
在右半部分有序区间内。例如,如果右半部分的元素是[1, 2, 3, 4, 5]
,而target = 5
,因为5
并不小于nums[right] = 5
,这个条件将无法匹配到5
。
为什么使用错误条件会得到错误答案?
在旋转排序数组中,我们必须精确判断目标值是否在有序区间内。如果使用错误条件 if (nums[mid] <= target && target < nums[right])
,就会漏掉当目标值等于右边界元素的情况,导致无法找到目标值,返回错误的结果(如返回-1
)。
举个例子帮助理解
假设数组是[4, 5, 6, 7, 0, 1, 2]
,target = 2
,那么:
nums[mid]
可能是0
,nums[right]
是2
。- 按照原条件
if (nums[mid] < target && target <= nums[right])
:0 < 2
为真,2 <= 2
也为真,条件成立,因此可以在右半部分继续查找。
- 按照错误条件
if (nums[mid] <= target && target < nums[right])
:0 <= 2
为真,但是2 < 2
为假,因此条件不成立,会错误地调整查找区间。
总结
原条件 if (nums[mid] < target && target <= nums[right])
保证了目标值即使等于右边界元素 nums[right]
时,仍然可以正确查找到。而错误条件 if (nums[mid] <= target && target < nums[right])
会遗漏目标值等于右边界的情况,从而导致错误答案。
相关文章:

Leetcode 搜索旋转排序数组
这段代码是用于解决LeetCode第33题“搜索旋转排序数组”的Java解法。以下是对该算法思想的中文解释: 算法思想 二分查找的基本思路: 由于数组是部分有序的(被旋转过),我们可以利用二分查找的思想,逐步缩小…...

Spring Task—定时任务
Spring Task 是 Spring 提供的一种轻量级定时任务调度功能,内置在 Spring 框架中。与 Quartz 等重量级调度框架相比,Spring Task 使用简便,无需额外依赖,适合在简单的调度任务场景中使用。通过注解配置方式,开发者可以…...

Spring Boot 应用开发概述
目录 Spring Boot 应用开发概述 Spring Boot 的核心特性 Spring Boot 的开发模式 Spring Boot 在企业应用开发中的优势 结论 Spring Boot 应用开发概述 Spring Boot 是由 Pivotal 团队开发的一个框架,基于 Spring 框架,旨在简化和加速基于 Spring …...

Chrome谷歌浏览器加载ActiveX控件之allWebDesktop控件介绍
背景 allWebDesktop控件是一款方便用户在线打开各类文档的OA办公控件。它设计比较轻巧,充分利用计算机程序资源打开文档,并将程序窗口嵌入到allWebDesktop控件区域内,从而实现浏览器内打开各类文档效果。 allWebPlugin中间件是一款为用户提供…...

GitHub Star 数量前 5 的开源应用程序生成器
欢迎来的 GitHub Star 数量排名系列文章的第 7 篇——最受欢迎的应用程序生成器。 之前我们已经详细探讨过:在 GitHub 上最受欢迎的——无代码工具、低代码项目、内部工具、CRUD项目、自部署项目和 Airtable 开源替代品。累计超过 50 个优质项目!&#…...

DBC文件当中新建CANFD等类型的报文
同学最近有添加CANFD报文的需求,需要用到CANFD类型报文的DBC文件,这下就难住我了,我之前用的DBC文件只有“CAN Standard”“CAN Extended”两种类型,压根没见过FD的。 后来他找到了项目之前的DBC,打开来看,…...

基于SpringBoot的房地产销售管理系统【附源码】
基于SpringBoot的房地产销售管理系统(源码L文说明文档) 目录 4 系统设计 4.1用户登录功能的详细实现 4.2管理员权限的功能实现 4.2.1客户信息管理功能的详细实现 4.2.2房产管理功能的详细实现 4.2.3预约看房功能的详细实现 4.2.4论…...

圆点虚线 Android
参考 https://blog.csdn.net/l_o_s/article/details/73550876 <com.xxx.wwww.weight.PointDividerViewandroid:layout_width"match_parent"android:layout_height"wrap_content"app:PDbackgroundColor"color/white"app:dotColor"color/…...

贵州鑫宏远农业-始终致力于推动现代农业的科技创新与发展
贵州鑫宏远农业科技有限公司,是一家在高科技农业领域深耕细作、锐意进取的企业。自成立以来,我们始终致力于推动现代农业的科技创新与发展,业务全面覆盖农业科学研发、组织培养生产、专业育苗培植、半成品及成品精细化养护、市场销售以及全方…...

程序员做销售,从代码到客户的逆袭之路
大家好,我是小悟。 在这个互联网风起云涌、技术迭代日新月异的时代,“跨界”已然成为一种新潮流。就好似那从天而降的大侠,一不小心就可能横跨了数个充满奇遇与挑战的领域。 想象一下,一个平日里只跟代码打交道的程序员…...
Flink CDC系列之:理解学习Kubernetes模式
Flink CDC系列之:理解学习Kubernetes模式 准备会话模式启动会话集群设置 Flink CDC提交 Flink CDC Job Kubernetes 是一种流行的容器编排系统,用于自动化计算机应用程序的部署、扩展和管理。Flink 的原生 Kubernetes 集成允许您直接在正在运行的 Kuberne…...
git合并相关操作详解
在使用Git进行分支管理时,合并(merge)操作是非常常见的。下面是Git合并相关的详细步骤和一些常见的场景及注意事项。 一、 基本合并操作 假设我们有两个分支:main 和 feature,希望将 feature 合并到 main 上。 切换到目标分支 首先需要切换到你想合并到的分支。例如,切…...

前端经典【面试题】持续更新HTML、CSS、JS、VUE、FLUTTER、性能优化等
HTML/CSS 面试题 什么是语义化 HTML? 说明:语义化 HTML 使用 HTML 标签来描述内容的含义,而不仅仅是其外观。使用语义化标签可以提高可读性和可访问性,并对 SEO 友好。示例: <header><h1>网站标题</h1&…...
【Linux知识】linux磁盘管理深入了解
文章目录 常见磁盘管理命令行磁盘分区NASNAS 磁盘挂载🔐 如何设置NAS设备的访问权限? Mkfs🧐 mkfs 命令支持哪些文件系统类型? Mount🔑 在Linux中,如何安全地卸载挂载的文件系统? 常见磁盘管理命…...
Qt Essential Classes
目录 QVariant QFlags QRandomGenerator 经典的Qt容器 QVector QList QMap QMultiMap QSet QHash QVariant 同std::variant是一样的,他是一个更加高级的union。在一个时间下,它虽然实际上只能是一种类型,但是一个variant可以hold住…...

小小猫棒onu替换家用光猫,薅运营商带宽羊毛,突破1000M
小小猫棒onu 一、总体步骤 1 记录原来光猫信息 主要包括SN,ploam密码,loid、loid密码、 mac、上网的vlan id等 一般gpon采用SN、ploam密码、SNploam密码三种中的一种认证方式 一般Epon采用loid(逻辑id)、mac、loid mac三种中…...

软件测试学习笔记丨Selenium学习笔记:css定位
本文转自测试人社区,原文链接:https://ceshiren.com/t/topic/22511 本文为霍格沃兹测试开发学社的学习经历分享,写出来分享给大家,希望有志同道合的小伙伴可以一起交流技术,一起进步~ 说明:本篇博客基于sel…...
python数据处理常用操作
数据处理是机器学习中非常重要的一步,以下是一些常用的操作和示例代码: 1. 数据清洗 处理缺失值: import pandas as pd# 读取数据 df pd.read_csv(data.csv)# 删除缺失值 df.dropna(inplaceTrue)# 用均值填充缺失值 df.fillna(df.mean(), i…...
解决minio跨域问题
MinIO 支持跨域资源共享(CORS),允许你配置跨域请求的相关策略。以下是一个基本的CORS配置示例,你可以在MinIO的配置文件(例如config.json)中设置这些策略: 在Linux中 root/.minio 目录下如果没有就新建一个 config.jso…...
python 跳过当前循环
在 Python 中,可以使用 continue 语句来跳过当前循环的剩余部分,并继续下一次循环。continue 语句用于跳过循环体中剩余的语句,并立即开始下一次迭代。 以下是一个简单的示例,演示了如何在 for 循环中使用 continue 语句…...
Android Wi-Fi 连接失败日志分析
1. Android wifi 关键日志总结 (1) Wi-Fi 断开 (CTRL-EVENT-DISCONNECTED reason3) 日志相关部分: 06-05 10:48:40.987 943 943 I wpa_supplicant: wlan0: CTRL-EVENT-DISCONNECTED bssid44:9b:c1:57:a8:90 reason3 locally_generated1解析: CTR…...
Golang 面试经典题:map 的 key 可以是什么类型?哪些不可以?
Golang 面试经典题:map 的 key 可以是什么类型?哪些不可以? 在 Golang 的面试中,map 类型的使用是一个常见的考点,其中对 key 类型的合法性 是一道常被提及的基础却很容易被忽视的问题。本文将带你深入理解 Golang 中…...
《Playwright:微软的自动化测试工具详解》
Playwright 简介:声明内容来自网络,将内容拼接整理出来的文档 Playwright 是微软开发的自动化测试工具,支持 Chrome、Firefox、Safari 等主流浏览器,提供多语言 API(Python、JavaScript、Java、.NET)。它的特点包括&a…...

iPhone密码忘记了办?iPhoneUnlocker,iPhone解锁工具Aiseesoft iPhone Unlocker 高级注册版分享
平时用 iPhone 的时候,难免会碰到解锁的麻烦事。比如密码忘了、人脸识别 / 指纹识别突然不灵,或者买了二手 iPhone 却被原来的 iCloud 账号锁住,这时候就需要靠谱的解锁工具来帮忙了。Aiseesoft iPhone Unlocker 就是专门解决这些问题的软件&…...

C# 类和继承(抽象类)
抽象类 抽象类是指设计为被继承的类。抽象类只能被用作其他类的基类。 不能创建抽象类的实例。抽象类使用abstract修饰符声明。 抽象类可以包含抽象成员或普通的非抽象成员。抽象类的成员可以是抽象成员和普通带 实现的成员的任意组合。抽象类自己可以派生自另一个抽象类。例…...
Unit 1 深度强化学习简介
Deep RL Course ——Unit 1 Introduction 从理论和实践层面深入学习深度强化学习。学会使用知名的深度强化学习库,例如 Stable Baselines3、RL Baselines3 Zoo、Sample Factory 和 CleanRL。在独特的环境中训练智能体,比如 SnowballFight、Huggy the Do…...

IoT/HCIP实验-3/LiteOS操作系统内核实验(任务、内存、信号量、CMSIS..)
文章目录 概述HelloWorld 工程C/C配置编译器主配置Makefile脚本烧录器主配置运行结果程序调用栈 任务管理实验实验结果osal 系统适配层osal_task_create 其他实验实验源码内存管理实验互斥锁实验信号量实验 CMISIS接口实验还是得JlINKCMSIS 简介LiteOS->CMSIS任务间消息交互…...
【生成模型】视频生成论文调研
工作清单 上游应用方向:控制、速度、时长、高动态、多主体驱动 类型工作基础模型WAN / WAN-VACE / HunyuanVideo控制条件轨迹控制ATI~镜头控制ReCamMaster~多主体驱动Phantom~音频驱动Let Them Talk: Audio-Driven Multi-Person Conversational Video Generation速…...
纯 Java 项目(非 SpringBoot)集成 Mybatis-Plus 和 Mybatis-Plus-Join
纯 Java 项目(非 SpringBoot)集成 Mybatis-Plus 和 Mybatis-Plus-Join 1、依赖1.1、依赖版本1.2、pom.xml 2、代码2.1、SqlSession 构造器2.2、MybatisPlus代码生成器2.3、获取 config.yml 配置2.3.1、config.yml2.3.2、项目配置类 2.4、ftl 模板2.4.1、…...
Vite中定义@软链接
在webpack中可以直接通过符号表示src路径,但是vite中默认不可以。 如何实现: vite中提供了resolve.alias:通过别名在指向一个具体的路径 在vite.config.js中 import { join } from pathexport default defineConfig({plugins: [vue()],//…...