LeetCode-Go 题解 153旋转排序数组最小值 findMin 的二分查找实现【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go导读本文围绕 LeetCode 153「Find Minimum in Rotated Sorted Array寻找旋转排序数组中的最小值」展开以 LeetCode-Go 仓库中该题的官方题解文档为主线完整剖析旋转数组的数学特征、三种 Go 实现的算法设计与复杂度并结合仓库内真实源码与单元测试用例逐一验证。读完本文你将掌握如何在 O(log n) 时间内定位旋转数组的分割点即最小值并理解暴力遍历与二分搜索两种思路的取舍为后续解决 154含重复元素与 33在旋转数组中搜索目标值等系列题目打下基础。题目定义什么是旋转排序数组题目描述如下见 题解文档Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand. Find the minimum element. You may assume no duplicate exists in the array.即一个按升序排列的数组在某个未知的旋转点pivot处被整体旋转例如[0,1,2,4,5,6,7]可能旋转为[4,5,6,7,0,1,2]要求找出其中的最小元素且保证数组内不存在重复元素。题目的两个官方示例示例 1 Input: [3,4,5,1,2] Output: 1 示例 2 Input: [4,5,6,7,0,1,2] Output: 0旋转数组的直观特征README.md 中的题目大意亦有阐述一个原本从小到大排序的数组在某一分割点被切分后两部分发生了对调数值偏大的那一段被放到了数组前部。因此整个数组由两段各自有序的子区间构成前一段的所有元素都大于后一段的所有元素最小值恰好位于两个有序区间的交界处。核心思路找最小值等价于找分割点解题思路见 题解文档 的 Solution Approach 与 README.md求数组的最小元素本质上就是寻找分割点该位置上的数满足前一个数比当前数大且后一个数也比当前数大由于数组被分割为两个有序区间可以采用二分搜索在需要搜索的有序区间内快速收缩时间复杂度为 O(log n)也可以使用暴力解法从头到尾遍历动态维护一个最小值时间复杂度为 O(n)。这一题目在 LeetCode-Go 仓库中对应三个解法实现源码位于 153. Find Minimum in Rotated Sorted Array.go下面逐一展开讲解。解法一标准二分findMin// Solution 1: Binary search func findMin(nums []int) int { low, high : 0, len(nums)-1 for low high { if nums[low] nums[high] { return nums[low] } mid : low (high-low)1 if nums[mid] nums[low] { low mid 1 } else { high mid } } return nums[low] }算法逐步推演单调性提前终止在每次进入循环时先判断nums[low] nums[high]。如果成立说明当前[low, high]区间已经是严格升序未发生旋转或已收缩到有序段此时区间最左端即为最小值直接返回nums[low]。中点计算mid : low (high-low)1采用low (high-low)/2的形式而非(lowhigh)/2避免了大整数相加溢出这是 Go 二分实现中的常见防御性写法位运算1等价于除以 2。区间收缩若nums[mid] nums[low]说明mid落在数值偏大的前半段旋转后的大数段最小值在右侧故low mid 1否则mid已落在包含最小值的后半段故high mid注意此处不是mid - 1因为mid本身可能就是最小值。循环退出当low high时循环结束此时nums[low]即全局最小值。边界情况与正确性数组完全有序如[1,2,3]首次循环即满足nums[0] nums[2]直接返回nums[0]数组长度为 1low high不进入循环返回唯一的元素旋转发生在末尾如[2,1]low0, high1nums[0] nums[1]不满足提前终止mid0nums[0] nums[0]成立low1循环结束返回nums[1]1正确。解法二带旋转检测与兜底的二分findMin1// Solution 2: Binary search func findMin1(nums []int) int { if len(nums) 0 { return 0 } if len(nums) 1 { return nums[0] } if nums[len(nums)-1] nums[0] { return nums[0] } low, high : 0, len(nums)-1 for low high { mid : low (high-low)1 if nums[low] nums[high] { return nums[low] } if (mid len(nums)-1 nums[mid-1] nums[mid]) || (mid len(nums)-1 mid 0 nums[mid-1] nums[mid] nums[mid] nums[mid1]) { return nums[mid] } if nums[mid] nums[low] nums[low] nums[high] { // mid is in the part with larger values low mid 1 } else if nums[mid] nums[low] nums[low] nums[high] { // mid is in the part with smaller values high mid - 1 } else { if nums[low] nums[mid] { low } if nums[high] nums[mid] { high-- } } } return -1 }与解法一的差异解法二是另一种二分写法特点是先做前置边界判断再在循环中显式判定分割点空数组与单元素空输入返回0题目保证输入合法此为防御性分支单元素直接返回该元素。整体有序判定若nums[len(nums)-1] nums[0]说明数组未发生有效旋转最小值就是首元素直接返回。分割点显式识别循环中一旦发现nums[mid-1] nums[mid] nums[mid] nums[mid1]即mid同时小于左右邻居它就是旋转的分割点立即返回nums[mid]对mid位于数组末端的情况单独处理mid len(nums)-1时只需检查nums[mid-1] nums[mid]。区间归属判断nums[mid] nums[low] nums[low] nums[high]mid处于数值较大的前半段low mid 1nums[mid] nums[low] nums[low] nums[high]mid处于数值较小的后半段high mid - 1其余情况如端点与中点相等通过low/high--逐指针推进作为兜底。兜底返回值若循环退出仍未命中返回-1。从源码注释看该分支是为全相等这类非法输入准备的兜底题目明确无重复元素正常输入不会走到。说明解法二比解法一更健壮但更冗长其额外的前置判断和显式分割点检测使得代码可读性略低。LeetCode-Go 仓库同时保留两种二分实现正是为了展示统一模板与显式判断两种二分风格供读者对比学习。解法三暴力遍历findMin2// Solution 3: Brute force func findMin2(nums []int) int { min : nums[0] for _, num : range nums[1:] { if min num { min num } } return min }暴力解法逻辑最为直白以首元素初始化最小值遍历剩余全部元素一旦发现更小值就更新。它不依赖数组的任何有序性质适用于任意数组但时间复杂度为 O(n)空间复杂度 O(1)。在数据量小或作为二分实现的对照基准时这种写法仍然有价值。三种解法复杂度对比解法核心策略时间复杂度空间复杂度备注findMin标准二分O(log n)O(1)推荐方案代码最精简findMin1二分 显式分割点判定O(log n)O(1)含边界/非法输入兜底findMin2线性扫描维护最小值O(n)O(1)不依赖有序性适合对照验证在数据规模 n 较大时O(log n) 与 O(n) 的差距非常明显这正是该题旋转数组 二分经典组合的意义所在。测试用例验证仓库为本题配备了完整的单元测试见 153. Find Minimum in Rotated Sorted Array_test.go测试覆盖了以下关键场景qs : []question153{ {para153{[]int{5, 1, 2, 3, 4}}, ans153{1}}, // 旋转点在中间偏右 {para153{[]int{1}}, ans153{1}}, // 单元素 {para153{[]int{1, 2}}, ans153{1}}, // 升序未旋转 {para153{[]int{2, 1}}, ans153{1}}, // 旋转 1 位 {para153{[]int{2, 3, 1}}, ans153{1}}, // 旋转点在最末 {para153{[]int{1, 2, 3}}, ans153{1}}, // 整体有序 {para153{[]int{3, 4, 5, 1, 2}}, ans153{1}}, // 官方示例 1 {para153{[]int{4, 5, 6, 7, 0, 1, 2}}, ans153{0}}, // 官方示例 2 {para153{[]int{3, 3, 1, 3}}, ans153{1}}, // 含重复元素的旋转边界 }测试逻辑要点每个用例同时调用findMin1与findMin2并与期望答案比对任一不符即t.Fatalf失败额外覆盖了findMin1的空输入分支期望返回0与全相等输入[2,2,2]的兜底分支期望返回-1保证防御性代码路径也被测试命中。这套表格驱动table-driven的测试风格贯穿 LeetCode-Go 仓库question153/para153/ans153的结构体封装让每个测试用例的输入输出一目了然既便于评审也便于回归。运行与验证方式如果你希望在本地复现该题解克隆仓库后进入题目目录git clone https://gitcode.com/GitHub_Trending/le/LeetCode-Go cd LeetCode-Go运行该题的单元测试go test ./leetcode/0153.Find-Minimum-in-Rotated-Sorted-Array/ -v测试通过时输出PASS并打印每个用例的输入输出对照。系列延伸从 153 到 154 与 33掌握 153 后可以顺藤摸瓜攻克同族题目均可在本仓库leetcode/目录下找到对应实现与文档154. Find Minimum in Rotated Sorted Array II与 153 的唯一区别是数组中允许存在重复元素。重复元素会破坏nums[mid] nums[low]一定落在前半段的判断依据因此需要在边界相等时逐步收紧指针解法二中的low/high--兜底思想正是为应对这类情况设计的最坏情况下时间复杂度退化为 O(n)。33. Search in Rotated Sorted Array在旋转数组中搜索指定目标值而非找最小值。核心思路依然是二分 判断mid落在哪一段有序区间再决定收缩方向与 153 的区间归属判断一脉相承。三者共用二分查找 有序区间判定这一底层模型建议按 153 → 154 → 33 的顺序循序渐进地练习。小结LeetCode-Go 仓库中 153 题的题解给出了从暴力 O(n)到二分 O(log n)的完整递进路径旋转数组 两个有序段拼接最小值即两段的交界处分割点findMin用最简二分在 O(log n) 内完成任务是面试与竞赛的首选写法findMin1展示了显式分割点判定与边界兜底可作为理解二分细节的进阶范本findMin2的暴力实现则作为正确性对照验证二分结果的可靠性。建议读者在本地用go test跑通 测试文件 中的全部用例再亲手在findMin中插入日志观察low/high/mid的收缩轨迹即可彻底吃透旋转数组二分的核心思想。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考