文章目录前言一、题目1、原题链接2、题目描述二、个人思路整理1、思路分析2、解题代码三、知识风暴前言本专栏文章为《LeetCode 热题 100》的刷题题解相关内容如有侵权立即删除。一、题目1、原题链接33.搜索旋转排序数组2、题目描述二、个人思路整理1、思路分析本题的核心在于旋转后的数组被任意mid切开后一定有一半是有序的另一半可能有序也可能包含旋转点。具体步骤计算中点mid若nums[mid] target直接返回mid。判断哪半部分有序如果nums[left] nums[mid]说明左半段[left, mid]是严格/单调升序的。判断target是否落在左半段范围内即nums[left] target target nums[mid]若在说明目标值在左半段收缩右边界right mid - 1若不在说明目标值在右半段收缩左边界left mid 1。否则nums[left] nums[mid]说明旋转点在左半段右半段[mid, right]必然是有序的。判断target是否落在右半段范围内即nums[mid] target target nums[right]若在说明目标值在右半段收缩左边界left mid 1若不在说明目标值在左半段收缩右边界right mid - 1。退出循环若left right仍未找到返回-1。2、解题代码classSolution{public:intsearch(vectorintnums,inttarget){intleft0;intrightnums.size()-1;// 标准闭区间二分查找 [left, right]while(leftright){// 防溢出写法计算中点intmidleft(right-left)/2;// 命中目标值直接返回下标if(nums[mid]target){returnmid;}// 判断哪部分是有序的// 1. 如果 nums[left] nums[mid]说明左半区间 [left, mid] 是单调递增的if(nums[left]nums[mid]){// 检查 target 是否落在有序的左半区间内if(nums[left]targettargetnums[mid]){rightmid-1;// 目标在左侧缩小右边界}else{leftmid1;// 目标在右侧缩小左边界}}else{// 2. 否则说明旋转断点在左侧右半区间 [mid, right] 必然是有序的// 检查 target 是否落在有序的右半区间内if(nums[mid]targettargetnums[right]){leftmid1;// 目标在右侧缩小左边界}else{rightmid-1;// 目标在左侧缩小右边界}}}// 遍历结束未找到目标值return-1;}};复杂度分析时间复杂度O ( log n ) O(\log n)O(logn)每次都将搜索区间减半。空间复杂度O ( 1 ) O(1)O(1)仅使用常数个额外指针变量。三、知识风暴二分查找Binary Search是本题的核心思想。它通过不断折半缩小搜索区间在有序数据中高效定位目标值。理解二分查找的区间定义、边界收缩与有序性判断对掌握本题至关重要。算法核心思想有序性前提二分查找要求数据在逻辑上严格有序。本题的数组虽经旋转但被任意mid切开后一定有一半是严格升序的我们正是利用这一半的有序性来决定收缩方向从而在O ( log n ) O(\log n)O(logn)时间内完成搜索。折半搜索本质每次取区间中点mid先判断哪一半有序再检查target是否落在该有序区间内据此将搜索区间缩小一半把时间复杂度从暴力遍历的O ( n ) O(n)O(n)降到O ( log n ) O(\log n)O(logn)。旋转数组的二分前提与普通有序数组不同旋转数组整体并非单调因此不能直接套用经典二分模板必须先定位有序半区再决定向哪一侧收缩。常见对比二分查找 vs 暴力遍历二分查找Binary Search利用部分有序性每次排除一半区间时间复杂度O ( log n ) O(\log n)O(logn)适合大规模数据的快速检索。暴力遍历线性扫描从头到尾扫描整个数组时间复杂度O ( n ) O(n)O(n)实现简单但效率低无法满足本题对O ( log n ) O(\log n)O(logn)的要求。共同点两者都能正确判断目标值是否存在。区别在于二分查找依赖有序性大幅减少比较次数而暴力遍历不依赖任何数据特性、但代价是线性时间。“区间边界”定义思想核心思想二分查找的边界定义决定了循环条件与收缩方式。本题采用闭区间[left, right]因此循环条件为left right收缩时left mid 1或right mid - 1保证区间始终有效。与本题的联系本题初始区间为[0, n - 1]每次比较中点元素后先判断哪一半有序再判断target是否落在有序半区内据此收缩边界直至区间为空仍未找到则返回-1。注意事项边界收缩必须严格跳过mid即mid ± 1否则可能陷入死循环同时用left (right - left) / 2计算中点可避免left right整数溢出。使用要点循环终止条件闭区间写法下当left right时区间为空说明目标不存在退出循环返回-1。单次迭代逻辑计算mid left (right - left) / 2若nums[mid] target直接返回否则判断nums[left] nums[mid]是否成立以确定左半段是否有序再决定收缩方向。有序半区的判断nums[left] nums[mid]成立说明左半段有序此时只需检查target是否落在[nums[left], nums[mid])内即可决定收缩方向否则右半段有序检查target是否落在(nums[mid], nums[right]]内。结果返回一旦nums[mid] target立即返回下标mid若循环结束仍未命中则说明目标不在数组中返回-1。算法变体与扩展搜索旋转排序数组 IILeetCode 81数组中允许重复元素此时nums[left] nums[mid]无法判断哪半有序需先收缩边界去重是本题的直接进阶版。寻找旋转排序数组中的最小值LeetCode 153不搜索目标值而是利用旋转点两侧的有序性二分定位最小值是旋转数组二分的另一经典应用。寻找峰值LeetCode 162利用相邻元素大小关系在无序数组中二分定位峰值体现二分思想不局限于严格有序数据。在排序数组中查找元素的第一个和最后一个位置LeetCode 34通过两次二分分别定位左右边界是二分查找处理重复元素的经典变体。相关 LeetCode 例题33. 搜索旋转排序数组二分 部分有序判断81. 搜索旋转排序数组 II二分 重复元素处理153. 寻找旋转排序数组中的最小值二分 旋转点定位162. 寻找峰值二分 局部单调性34. 在排序数组中查找元素的第一个和最后一个位置二分 边界定位
企业数字化 ERP 产品动态
相关推荐
2026年实测！职场新人语音转文字神器：从录音转写到AI总结的TaoToken配置指南 /* MD / 富文本中的 .toc（含博客园搬家等嵌套结构）；.toc-box 在侧栏，不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p（:empty 仍占 20px），一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/9/24 9:28:43
2026最新可靠性工程师避坑指南：面试被问原理答不上来？ 2026最新可靠性工程师避坑指南：面试被问原理答不上来？ 面试被问“如何保证高可用”时，你脑子里只蹦出“加冗余”三个字，结果面试官追问底层原理，你卡壳了。这种尴尬在2026最新的招聘市场中愈发常见，尤其是对于想转行或刚入行的 可靠性工程师… · 2026/9/24 9:28:45
2026最新满脸痘痘怎么办前端实战避坑指南 2026最新满脸痘痘怎么办前端实战避坑指南 学会语法却不知怎么搭项目，这是很多刚入行前端或转岗劳务班组负责人的通病。你背熟了 HTML 标签，也记住了 CSS 属性，甚至能写出几行 JavaScript… · 2026/9/23 9:26:04
智谱ZCode信任风波，唐杰“当学”马斯克 作者：Evin编辑：刘致呈审核：徐徐出品：互联网江湖据环球时报等媒体消息，最近，有多名使用智谱开发的AI编程工具ZCode的用户爆料称，他们发现该工具会未经用户许可，“静默上传”用户的编程… · 2026/9/24 9:28:44
iOS开发十年演进：从UIKit到SwiftUI与AI时代的生存指南 /* MD / 富文本中的 .toc（含博客园搬家等嵌套结构）；.toc-box 在侧栏，不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p（:empty 仍占 20px），一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/9/24 9:28:44
RedwoodRecord 实战指南：基于 Prisma 的 Redwood 原生 ORM 全解析 后端前端Web框架开发工具 【免费下载链接】redwood RedwoodGraphQL 项目地址： https://gitcode.com/gh_mirrors/re/redwood 点击查看 免费下载 RedwoodRecord 是 Redwood 框架内置的实验性 ORM（对象关系映射）层，它构建在 Prisma … · 2026/9/24 9:28:44
窗口的本质 窗口的本质
前置基础
1）虚拟内存
● 每个进程 4GB 虚拟地址：0x00000000 ~ 0xFFFFFFFF
● 用户空间：0x00000000 ~ 0x7FFFFFFF（低 2GB，进程私有）
● 内核空间：0x80000000 ~ 0xFFFFFFFF（… · 2026/9/24 9:28:38
Airbyte source-youtube-data 连接器工程剖析：增量策略、错误处理与配额治理实战 数据工程数据集成ETL后端大数据 【免费下载链接】airbyte Open-source data movement for ELT pipelines and AI agents — from APIs, databases & files to warehouses, lakes, and AI applications. Both self-hosted and Cloud. 项目地址： https://gitcode.… · 2026/9/24 9:28:37
自适应斜坡补偿：如何兼顾峰值电流模式稳定与动态响应 /* MD / 富文本中的 .toc（含博客园搬家等嵌套结构）；.toc-box 在侧栏，不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p（:empty 仍占 20px），一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/9/24 9:28:19
基于YOLOv8的渔船作业监控系统：从环境搭建到边缘部署全流程 简介：这是一套面向计算机、人工智能、自动化等专业学生与教师的毕业设计级项目资源，围绕YOLOv8实现渔船作业监控系统，可用于毕设、课程设计、大作业或项目立项演示。压缩包共97个文件，约24.21MB，以70个Python源码文件为… · 2026/9/24 0:00:13
1D-CNN时间序列建模实战：从Conv1d原理到工业落地 简介：面向时间序列数据建模的一维卷积神经网络完整实现，适合深度学习入门者及需要快速验证时序模型的研究者，能够从音频、文本、传感器或股价等序列中挖掘局部特征与时间依赖。压缩包体积很小，只有3KB，内含3个Python脚… · 2026/9/24 0:00:26
柔软的L：汉语语流中被忽视的舌肌张力控制 1. 这个“L”不是字母表里的L，而是舌尖上的L最近在几个方言群和语音教学社群里，反复看到有人发一句：“也说字母L：柔软的长舌”。初看以为是英语发音课笔记，点开才发现全是方言爱好者、播音系学生、语言康复师甚至戏曲演… · 2026/9/24 0:00:44
