LeetCode - 153. 寻找旋转排序数组中的最小值
题目
153. 寻找旋转排序数组中的最小值 - 力扣（LeetCode）
思路
旋转排序数组有一个关键特性：将一个排序数组在某个位置旋转后，会形成两个排序子数组，而最小值正好是第二个子数组的第一个元素。
使用二分查找来定位旋转点（最小值）。关键是比较中间元素与右边界元素的大小关系，根据比较结果确定最小值在哪个半区。
判断依据
如果 nums[mid] > nums[right]：
- 说明中间元素位于第一个递增子数组
- 最小值一定在 mid 右侧
- 更新 left = mid + 1
如果 nums[mid] < nums[right]：
- 说明中间元素位于第二个递增子数组
- 最小值可能是 mid 或在 mid 左侧
- 更新 right = mid
如果 nums[mid] == nums[right]：
- 在本题中（无重复元素），这种情况只会出现在 mid == right
- 将其归入第二种情况处理
算法步骤
初始化左右指针：left = 0, right = nums.size() - 1
当 left < right 时循环：
- 计算中点：mid = left + (right - left) / 2
- 比较 nums[mid] 与 nums[right]
- 根据比较结果更新 left 或 right
循环结束时，left == right，指向最小值
返回 nums[left]
过程
以数组 [4, 5, 6, 7, 0, 1, 2] 为例：
初始状态：
索引: 0 1 2 3 4 5 6
数组: [4, 5, 6, 7, 0, 1, 2]↑ ↑ ↑left mid right第一次迭代：
- mid = 3, nums[mid] = 7, nums[right] = 2
- 7 > 2，说明最小值在右半部分
- 更新 left = mid + 1 = 4
索引: 0 1 2 3 4 5 6
数组: [4, 5, 6, 7, 0, 1, 2]↑ ↑ ↑left mid right第二次迭代：
- mid = 5, nums[mid] = 1, nums[right] = 2
- 1 < 2，说明最小值在左半部分（包括mid）
- 更新 right = mid = 5
索引: 0 1 2 3 4 5 6
数组: [4, 5, 6, 7, 0, 1, 2]↑ ↑left rightmid第三次迭代：
- mid = 4, nums[mid] = 0, nums[right] = 1
- 0 < 1，说明最小值在左半部分（包括mid）
- 更新 right = mid = 4
索引: 0 1 2 3 4 5 6
数组: [4, 5, 6, 7, 0, 1, 2]↑leftrightmid
循环结束：
- left == right == 4
- 返回 nums[4] = 0
特殊情况
如果数组没有旋转（例如 [1, 2, 3, 4, 5]），算法仍然有效：
- nums[mid] 始终小于 nums[right]
- right 会不断向左移动
- 最终 left == right == 0，返回 nums[0]
时间复杂度
O(log n) - 二分查找的标准时间复杂度
空间复杂度
O(1) - 只使用常数额外空间
读者可能的错误写法
class Solution {
public:int findMin(vector<int>& nums) {int left = 0;int right = nums.size()-1;while(left <= right){int mid = left + (right - left)/2;if(nums[mid] > nums[right]){left = mid +1;}if(nums[mid] < nums[right]){right = mid -1;}if(nums[mid] == nums[right]){return mid;}}return right;}
};逻辑结构错误：你使用了三个独立的 if 语句，而不是 if-else if-else 结构。这意味着多个条件可能会同时执行，导致错误的更新。
错误的终止条件：当 nums[mid] == nums[right] 时，直接返回 mid。但这并不一定是最小值，特别是在有重复元素的情况下。
循环结束逻辑：使用 left <= right 作为循环条件，但循环结束后返回 right 可能不正确。
查找策略错误：当 nums[mid] < nums[right] 时，你排除了 mid（设置 right = mid - 1），但实际上 mid 可能就是最小值。
或者这样的错误写法
class Solution {
public:int findMin(vector<int>& nums) {int left = 0;int right = nums.size()-1;while(left < right){int mid = left + (right - left)/2;if(nums[mid] > nums[right]){left = mid +1;}if(nums[mid] < nums[right]){right = mid;}}return right;}
};你使用了两个独立的 if 语句，而不是 if-else 结构。这可能导致逻辑错误，特别是当 nums[mid] == nums[right] 的情况没有被处理。
正确的写法
class Solution {
public:int findMin(vector<int>& nums) {int left = 0;int right = nums.size()-1;while(left < right){int mid = left + (right - left)/2;if(nums[mid] > nums[right]){left = mid +1;}else{right = mid;}}return nums[right];}
};