二分查找进阶：旋转排序数组的两道经典题深度解析

目录一、搜索旋转排序数组LeetCode 33・中等题目描述解题思路Java 代码实现标准二分版复杂度分析核心知识点总结二、寻找旋转排序数组中的最小值LeetCode 153・中等题目描述解题思路Java 代码实现标准二分版复杂度分析核心知识点总结大家好今天我们来拆解两道二分查找的经典中等题搜索旋转排序数组和寻找旋转排序数组中的最小值。这两道题是二分查找从「有序数组」到「部分有序数组」的核心变形吃透它们能帮你彻底掌握二分查找的边界判断和灵活应用是算法面试的高频考点。一、搜索旋转排序数组LeetCode 33・中等题目描述整数数组nums按升序排列数组中的值互不相同。在传递给函数之前nums在预先未知的某个下标k0 k nums.length上进行了旋转使数组变为[nums[k], nums[k1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]下标从 0 开始计数。给你旋转后的数组nums和一个整数target如果nums中存在这个目标值target则返回它的下标否则返回-1。你必须设计一个时间复杂度为O(log n)的算法解决此问题。示例plaintext输入nums [4,5,6,7,0,1,2], target 0 输出4 输入nums [4,5,6,7,0,1,2], target 3 输出-1解题思路旋转排序数组的核心特性数组被分成了两个有序的子数组。比如[4,5,6,7,0,1,2]被分成了[4,5,6,7]和[0,1,2]两个升序子数组。二分查找的关键每次二分后一定有一半是完全有序的我们通过判断哪一半有序来缩小搜索范围计算中间位置mid判断mid所在的左半区[left, mid]是否有序nums[left] nums[mid]如果左半区有序若target在左半区范围内nums[left] target nums[mid]则搜索左半区否则搜索右半区如果右半区有序nums[mid] nums[right]若target在右半区范围内nums[mid] target nums[right]则搜索右半区否则搜索左半区若nums[mid] target直接返回mid循环结束未找到则返回-1Java 代码实现标准二分版java运行public class SearchRotatedSortedArray { 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; } } } return -1; // 未找到目标值 } }复杂度分析时间复杂度O(logn)二分查找每次将搜索范围缩小一半时间复杂度为对数级。空间复杂度O(1)仅使用常数级额外空间。核心知识点总结旋转数组特性二分后必有一半是完全有序的这是二分查找的核心依据。边界判断必须用nums[left] nums[mid]判断左半区有序避免left mid时的边界错误。目标范围判断必须严格判断目标是否在有序区间内避免漏判或错判。二、寻找旋转排序数组中的最小值LeetCode 153・中等题目描述已知一个长度为n的数组预先按照升序排列经由1到n次旋转后得到输入数组。例如原数组nums [0,1,2,4,5,6,7]在变化后可能得到若旋转4次则可以得到[4,5,6,7,0,1,2]若旋转7次则可以得到[0,1,2,4,5,6,7]给你一个元素值互不相同的数组nums它原来是一个升序排列的数组并按上述情形进行了多次旋转。请你找出并返回数组中的最小元素。你必须设计一个时间复杂度为 O(logn) 的算法解决此问题。示例plaintext输入nums [3,4,5,1,2] 输出1 解释原数组为 [1,2,3,4,5] 旋转 3 次得到输入数组。 输入nums [4,5,6,7,0,1,2] 输出0解题思路旋转排序数组的最小值就是两个有序子数组的分界点旋转点。二分查找的核心逻辑计算中间位置mid比较nums[mid]和nums[right]若nums[mid] nums[right]说明[mid, right]是有序的最小值在[left, mid]区间包含mid若nums[mid] nums[right]说明[left, mid]是有序的最小值在[mid1, right]区间循环结束时left right指向的就是最小值Java 代码实现标准二分版java运行public class FindMinInRotatedSortedArray { public int findMin(int[] nums) { int left 0; int right nums.length - 1; // 当left right时循环结束指向最小值 while (left right) { int mid left (right - left) / 2; // mid所在的右半区有序最小值在左半区包含mid if (nums[mid] nums[right]) { right mid; } else { // mid所在的左半区有序最小值在右半区不包含mid left mid 1; } } return nums[left]; } }复杂度分析时间复杂度O(logn)二分查找每次将搜索范围缩小一半时间复杂度为对数级。空间复杂度O(1)仅使用常数级额外空间。核心知识点总结分界点判断通过nums[mid]和nums[right]的比较快速定位最小值所在区间是这道题的核心技巧。循环条件使用left right避免left right时的死循环循环结束时left就是最小值下标。边界处理当nums[mid] nums[right]时right mid保留mid因为mid可能是最小值当nums[mid] nums[right]时left mid 1排除mid因为mid一定不是最小值。