LeetCode 153. 旋转排序数组找最小值：二分最优思路

LeetCode中等难度的经典题目——153. 寻找旋转排序数组中的最小值。这道题的核心考点是「二分查找」难点在于如何利用“旋转排序数组”的特性在O(log n)时间复杂度内找到最小值也是面试中常考的二分变形题。一、题目解读读懂旋转排序数组首先我们得先搞懂「旋转排序数组」到底是什么。题目里说原数组是升序排列的经过1到n次旋转后得到输入数组。这里的“旋转”很简单每次旋转就是把数组最后一个元素移到最前面。举个例子更直观原升序数组[0,1,2,4,5,6,7]旋转4次把最后一个元素依次移到前面最终得到 [4,5,6,7,0,1,2]旋转7次相当于旋转了一圈回到原数组 [0,1,2,4,5,6,7]题目给出的关键条件数组元素互不相同这个条件很重要能简化判断避免边界陷阱要求我们找到数组中的最小元素并且必须设计时间复杂度为O(log n)的算法。为什么不能用遍历O(n)因为题目明确要求O(log n)而二分查找的时间复杂度正好是O(log n)所以这道题的核心思路就是「二分查找」的变形。二、核心思路二分查找如何适配旋转数组普通二分查找是在有序数组中找目标值而旋转排序数组的特点是它被分成了两个升序子数组且前一个子数组的所有元素都大于后一个子数组的所有元素比如 [4,5,6,7,0,1,2]前半段 [4,5,6,7] 升序后半段 [0,1,2] 升序且 7 0。最小值就是这两个子数组的“分界点”——前一个子数组的最后一个元素后一个子数组的第一个元素。我们的目标就是通过二分查找快速定位到这个分界点。二分查找的关键的是「确定边界收缩方向」这里我们以「中间元素 nums[mid] 和右边界元素 nums[high] 比较」为判断依据原因很简单右边界的元素一定属于其中一个升序子数组能帮我们快速锁定最小值所在的区间。关键判断逻辑重中之重如果 nums[mid] nums[high]说明 mid 所在的位置已经在「右半段升序子数组」中因为右半段是升序的mid 比 high 小说明 mid 到 high 都是升序此时最小值一定在 mid 及其左边所以收缩右边界high mid。如果 nums[mid] nums[high]说明 mid 所在的位置还在「左半段升序子数组」中左半段所有元素都比右半段大此时最小值一定在 mid 的右边所以收缩左边界low mid 1。为什么不用 nums[mid] 和 nums[low] 比较大家可以思考一下如果数组没有旋转就是原升序数组nums[mid] 一定大于 nums[low]此时最小值在左边但如果数组旋转了比如 [3,4,5,1,2]nums[mid]5大于 nums[low]3但最小值却在右边这样判断会出错。所以用 nums[mid] 和 nums[high] 比较是最稳妥的。三、代码解析逐行看懂核心逻辑题目给出的代码非常简洁只有几行但每一行都有其作用我们逐行拆解functionfindMin(nums:number[]):number{letlow0;// 左边界指针初始指向数组第一个元素lethighnums.length-1;// 右边界指针初始指向数组最后一个元素while(lowhigh){// 循环条件左边界 右边界当low high时就是最小值所在位置constmidMath.floor((highlow)/2);// 计算中间索引避免溢出也可以用 (low high) 1if(nums[mid]nums[high]){// 中间元素 右边界元素最小值在左区间highmid;// 收缩右边界到mid注意不是mid-1因为mid可能就是最小值}else{// 中间元素 右边界元素最小值在右区间lowmid1;// 收缩左边界到mid1mid不可能是最小值直接跳过}}returnnums[low];// 循环结束后low high就是最小值的索引};代码细节注意点mid 的计算Math.floor((high low) / 2) 是最基础的写法也可以用位运算 (low high) 1效果相同效率更高但要注意避免 low high 溢出本题中数组长度不会太大溢出概率极低。循环条件low high而不是 low ≤ high。因为当 low high 时已经找到了最小值循环可以终止直接返回 nums[low] 即可。high mid 而非 mid-1因为当 nums[mid] nums[high] 时mid 有可能就是最小值比如数组 [2,1]mid0nums[mid]2 nums[high]1执行 lowmid11循环结束返回 nums[1]1再比如 [3,1,2]mid1nums[mid]1 nums[high]2执行 highmid1循环结束返回 1。如果写成 highmid-1可能会跳过最小值。low mid 1因为当 nums[mid] nums[high] 时mid 一定不是最小值比如 [4,5,6,7,0,1,2]mid3nums[mid]7 nums[high]2最小值在 mid 右边所以直接让 lowmid1。四、考点总结与拓展思考考点总结这道题的核心是「二分查找的变形」重点考查对“旋转排序数组”特性的理解以及如何确定二分查找的边界收缩方向。关键在于抓住“旋转数组的两个升序子数组右半段所有元素小于左半段”这一特点通过 mid 和 high 的比较快速锁定最小值所在区间。时间复杂度O(log n)二分查找的经典时间复杂度空间复杂度O(1)只用到了3个变量low、high、mid没有额外空间开销。拓展思考进阶如果题目修改为「数组元素可能重复」比如 nums [2,2,2,0,1]此时原代码还能生效吗答案是不能。因为当 nums[mid] nums[high] 时我们无法判断最小值在左还是右比如 [2,0,2,2,2] 和 [2,2,2,0,2]mid 和 high 都是2但最小值位置不同。这种情况下我们需要增加一个处理逻辑当 nums[mid] nums[high] 时让 high–缩小范围因为重复元素不影响最小值的查找修改后的代码可以应对元素重复的情况有兴趣的同学可以自行尝试编写。五、最后总结LeetCode 153 是一道非常经典的二分变形题难度中等适合巩固二分查找的思路。解题的关键在于理解旋转排序数组的结构两个升序子数组分界点为最小值选择正确的比较对象mid 和 high确定边界收缩方向注意边界细节比如 high mid 而非 mid-1。