描述

有一个长度为 n 的非降序数组，例如 [1, 2, 3, 4, 5]，将它进行旋转，即把数组最开始的若干个元素搬到数组的末尾，变成一个旋转数组，比如变成 [3, 4, 5, 1, 2]，或者 [4, 5, 1, 2, 3] 这样的。给定一个旋转数组，求数组中的最小值。

数据范围：

• 1 ≤ n ≤ 10000
• 数组中任意元素的值：0 ≤ val ≤ 10000

要求：

• 时间复杂度：O(logn)
• 空间复杂度：O(1)

示例

示例 1

输入：

[3, 4, 5, 1, 2]

返回值：

1

示例 2

输入：

[3, 100, 200, 3]

返回值：

3

解题思路

在这道题中，我们需要使用二分法来提高查找效率，从而将线性时间复杂度降低为对数级别。旋转数组的特性使得我们可以利用二分法，逐步缩小搜索范围。

算法流程

1. 初始化：声明 left 和 right 双指针，分别指向数组的左右两端。
2. 循环二分：设定中点 mid = (left + right) / 2，每次通过比较 nums[mid] 和 nums[right] 来决定下一步搜索范围：
   • 如果 nums[mid] > nums[right]，说明旋转点位于右半部分，最小值在 [mid + 1, right] 区间。
   • 如果 nums[mid] < nums[right]，说明旋转点位于左半部分，最小值在 [left, mid] 区间。
   • 如果 nums[mid] == nums[right]，无法判断旋转点位置，此时将 right-- 缩小范围。
3. 返回最小值：当 left == right 时，跳出循环，此时 left 和 right 都指向旋转数组中的最小值。

代码实现

int minNumberInRotateArray(int* nums, int numsLen) {// 如果数组没有旋转，直接返回最左边的元素if (nums[0] < nums[numsLen - 1]) {return nums[0];}int left = 0, mid = 0, right = numsLen - 1;// 使用二分法查找最小值while (left < right) {mid = left + (right - left) / 2;  // 计算中点if (nums[mid] > nums[right]) {// mid在左侧有序部分，最小值在右边left = mid + 1;} else if (nums[mid] < nums[right]) {// mid在右侧有序部分，最小值在左边right = mid;} else {// nums[mid] == nums[right]时，无法判断最小值在哪一侧right--;}}return nums[left];  // 返回最小值
}

关键点解释

1. 判断数组是否有序：

   • 如果数组未旋转（即 nums[0] < nums[numsLen - 1]），直接返回最小值 nums[0]。

2. 二分法的核心判断条件：

   • nums[mid] > nums[right]：旋转点在右侧，最小值在 [mid + 1, right]。
   • nums[mid] < nums[right]：旋转点在左侧，最小值在 [left, mid]。
   • nums[mid] == nums[right]：无法判断旋转点在左侧还是右侧，缩小右边界 right--。

3. 为什么要用 right-- 而不是 right = mid：

   • 当 nums[mid] == nums[right] 时，无法确定旋转点的位置，right-- 是为了收缩右边界，逐步缩小搜索范围，最终能够找到最小值。

举例分析

示例 1：[3, 4, 5, 1, 2]

1. 初始时，left = 0，right = 4。
2. 中点 mid = 2，比较 nums[mid] = 5 和 nums[right] = 2，因为 nums[mid] > nums[right]，说明旋转点在右边，更新 left = mid + 1 = 3。
3. 然后，left = 3，right = 4，计算新的 mid = 3，比较 nums[mid] = 1 和 nums[right] = 2，因为 nums[mid] < nums[right]，说明最小值在左边，更新 right = mid = 3。
4. 此时 left = right = 3，跳出循环，返回 nums[left] = 1。

示例 2：[3, 100, 200, 3]

1. 初始时，left = 0，right = 3。
2. 中点 mid = 1，比较 nums[mid] = 100 和 nums[right] = 3，因为 nums[mid] > nums[right]，更新 left = mid + 1 = 2。
3. 然后，left = 2，right = 3，计算新的 mid = 2，比较 nums[mid] = 200 和 nums[right] = 3，因为 nums[mid] > nums[right]，更新 left = mid + 1 = 3。
4. 此时 left = right = 3，跳出循环，返回 nums[left] = 3。

总结

其实这题整体上还是比较简单的。按照二分法的思路，其实还是比较好理解的。很快就能写出代码来，但是真正的难题是，如果遇到数组为[1,1,0,1,1,1]的情况，立刻就完蛋了。思考了半天，还是去参考了别人的代码。不太理解为什么用 right-- 而不是 right = mid
后来思考了下才理解，当 nums[mid] == nums[right] 时，我们无法确定 mid 和 right 哪个位置是有序的，因此只能将 right 向左移动一个位置。这是因为即使 mid 和 right 相等，right-- 仍然能保证范围逐渐缩小，最终能找到最小值。不理解为什么用right，而不是left。思考了半天，最后还是放弃了，背就完了。