算法二刷复盘｜旋转排序数组二分双杀（LeetCode 33 153）

目录一、LeetCode 33搜索旋转排序数组题目描述核心思路二分 有序区间判断Java 完整实现复杂度分析二、LeetCode 153寻找旋转排序数组中的最小值题目描述核心思路二分 无序区间定位Java 完整实现复杂度分析三、两道题核心对比四、二刷复盘感悟二刷二分查找必须拿下旋转排序数组的两道高频变形题。这两道题都是普通二分的进阶应用核心是利用「旋转后数组必有一半有序」的特性在对数级时间内完成搜索也是面试中二分变形的必考题。一、LeetCode 33搜索旋转排序数组题目描述整数数组nums按升序排列在某个点上进行了旋转例如[0,1,2,4,5,6,7]变为[4,5,6,7,0,1,2]。在数组中搜索目标值target如果存在返回索引否则返回-1。要求算法时间复杂度为 O (log n)。核心思路二分 有序区间判断普通二分无法直接用于旋转数组关键是每次二分后总有一半区间是有序的计算mid判断左半区间[left, mid]是否有序nums[left] nums[mid]若左半有序且target在[nums[left], nums[mid]]范围内则收缩右边界到mid-1否则目标一定在右半区间收缩左边界到mid1若右半区间[mid, right]有序nums[mid] nums[right]且target在[nums[mid], nums[right]]范围内则收缩左边界到mid1否则目标一定在左半区间收缩右边界到mid-1循环结束仍未找到返回-1。Java 完整实现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]) { // target在左半有序区间内收缩右边界 if (target nums[left] target nums[mid]) { right mid - 1; } else { // 否则目标在右半无序区间 left mid 1; } } else { // 右半区间有序 if (target nums[mid] target nums[right]) { // target在右半有序区间内收缩左边界 left mid 1; } else { // 否则目标在左半无序区间 right mid - 1; } } } return -1; } }复杂度分析时间复杂度O (log n)标准二分查找的对数级复杂度空间复杂度O (1)原地操作无额外空间开销。二、LeetCode 153寻找旋转排序数组中的最小值题目描述已知一个长度为n的数组预先按照升序排列经过了多次旋转每次旋转将最右侧元素移到最左侧。例如原数组[0,1,2,4,5,6,7]旋转后可能为[4,5,6,7,0,1,2]。请找出数组中的最小值数组无重复元素要求时间复杂度为 O (log n)。核心思路二分 无序区间定位和 33 题类似核心还是利用「必有一半有序」的特性若nums[mid] nums[right]说明最小值一定在右半无序区间将左边界移动到mid 1若nums[mid] nums[right]说明右半区间有序最小值一定在左半区间包括mid将右边界移动到mid循环结束时left right即为最小值的索引。Java 完整实现java运行class Solution { public int findMin(int[] nums) { int left 0; int right nums.length - 1; while (left right) { int mid left (right - left) / 2; // mid right 说明最小值在右半无序区间 if (nums[mid] nums[right]) { left mid 1; } else { // 右半有序最小值在左半含mid right mid; } } return nums[left]; } }复杂度分析时间复杂度O (log n)标准二分查找的对数级复杂度空间复杂度O (1)原地操作无额外空间开销。三、两道题核心对比表格对比项LeetCode 33 搜索目标值LeetCode 153 找最小值核心考点有序区间判断 目标值定位无序区间定位 最小值边界关键逻辑每次判断哪一半有序再判断目标是否在有序区间每次通过nums[mid]和nums[right]比较定位最小值所在区间循环条件left right普通二分模板left right边界逼近模板面试高频问题如何处理数组无旋转的情况如何判断有序区间为什么用nums[mid]和nums[right]比较不用nums[left]四、二刷复盘感悟二分变形的核心是「有序区间的判断」不管数组如何旋转只要是升序旋转数组每次二分后必然有一半区间是有序的这是解题的关键突破口边界模板要区分使用场景33 题用left right的普通二分模板153 题用left right的边界逼近模板不同场景下选择合适的模板能减少边界错误拓展延伸如果数组存在重复元素如 LeetCode 81 题判断有序区间时需要额外处理nums[left] nums[mid] nums[right]的情况此时只能left收缩边界最坏时间复杂度会退化为 O (n)。