文章目录前言一、题目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. 在排序数组中查找元素的第一个和最后一个位置二分 边界定位 
长河君 · 2026/9/23 9:26:21 · 阅读 1.2k 【二分查找】LC 33.搜索旋转排序数组
文章目录前言一、题目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. 在排序数组中查找元素的第一个和最后一个位置二分 边界定位