LeetCode 153. 寻找旋转排序数组中的最小值（C语言题解）
一、题目描述
已知一个长度为n的数组，原本按升序排列，但在某个未知位置进行了旋转，例如：
原数组: [0,1,2,4,5,6,7] 旋转后可能变为: [4,5,6,7,0,1,2]现在给定旋转后的数组nums，要求找出数组中的最小值。
要求：
时间复杂度必须为O(log n)。
二、解题思路（二分查找）
由于数组原本是升序排列的，只是被旋转了一次，因此数组可以看作两段有序区间：
[较大的一段] + [较小的一段]例如：
[4,5,6,7 | 0,1,2]最小值就是第二段的第一个元素。
因此可以使用二分查找来定位这个位置。
核心判断
设：
left = 0 right = n - 1 mid = (left + right) / 2比较nums[mid]和nums[right]：
情况1：nums[mid] > nums[right]
说明mid在左半部分递增区间
[4,5,6,7 | 0,1,2] ↑ mid最小值一定在右边
left = mid + 1情况2：nums[mid] < nums[right]
说明mid在右半部分递增区间
[4,5,6,7 | 0,1,2] ↑ mid最小值在mid 或左侧
right = mid当left == right时，循环结束，此时位置就是最小值。
三、C语言代码实现
int findMin(int* nums, int numsSize) { int left = 0; int right = numsSize - 1; while (left < right) { int mid = left + (right - left) / 2; if (nums[mid] > nums[right]) { // 最小值在右半部分 left = mid + 1; } else { // 最小值在左半部分（包含mid） right = mid; } } return nums[left]; }四、示例分析
示例
输入: nums = [4,5,6,7,0,1,2] 输出: 0执行过程：
left=0 right=6 mid=3 nums[mid]=7 > nums[right]=2 → left=4 left=4 right=6 mid=5 nums[mid]=1 < nums[right]=2 → right=5 left=4 right=5 mid=4 nums[mid]=0 < nums[right]=1 → right=4 left=4 right=4 结束最小值为：
nums[4] = 0五、复杂度分析
| 类型 | 复杂度 |
|---|---|
| 时间复杂度 | O(log n) |
| 空间复杂度 | O(1) |
二分查找每次可以排除一半区间，因此时间复杂度为log n。
六、总结
本题的关键在于理解：
旋转数组 = 两段递增数组
利用
nums[mid]和nums[right]判断最小值所在区间通过二分查找不断缩小范围
这是旋转数组系列问题的基础题，和以下题目属于同一类型：
33. 搜索旋转排序数组
81. 搜索旋转排序数组 II
154. 寻找旋转排序数组中的最小值 II
掌握这种二分查找的区间判断方法，可以解决大部分旋转数组问题。