寻找旋转排序数组中的最小值

题目描述：假设一个按照升序排列的数组在某个未知点上进行了旋转。例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2]。请找出其中最小的元素。你可以假设数组中不存在重复元素。

解题过程：

1. 问题理解与分析

   • 核心特征：数组原本是严格递增（无重复元素）的，但在某个点进行了旋转。这意味着数组由两个递增的子数组拼接而成。
   • 关键观察：旋转后的数组虽然整体无序，但它的两部分内部仍然是有序的。最小值恰好是第二个递增子数组的第一个元素，也是整个数组的“拐点”。
   • 目标：高效地找到这个最小值。一个简单的方法是遍历整个数组，时间复杂度是 O(n)。但利用数组“部分有序”的特性，我们可以使用二分查找算法在 O(log n) 的时间内解决。

2. 算法思路：二分查找

   • 核心思想：在标准的二分查找中，我们通过与中间值比较来决定搜索左半部分还是右半部分。在这个问题中，我们需要找到一个判断条件，能够确定最小值位于当前中间点的左侧还是右侧。
   • 关键比较：将数组的中间元素 nums[mid] 与数组的最右元素 nums[high] 进行比较。这个比较是解决问题的精髓。
     • 在一个标准的、未旋转的升序数组中，nums[mid] 总是小于 nums[high]。
     • 在旋转数组中：
       • 如果 nums[mid] < nums[high]：这说明从 mid 到 high 的这个区间是严格递增的。那么，最小值一定不在 (mid, high] 这个区间内（包括 mid 本身有可能是最小值），最小值只可能存在于 [low, mid] 这个区间（包括 mid）。因此，我们将搜索范围缩小到左半部分，即 high = mid。
       • 如果 nums[mid] > nums[high]：这说明从 mid 到 high 的这个区间不是完全递增的，中间必然包含了旋转的“拐点”（即最小值）。因此，最小值一定存在于 (mid, high] 这个区间内。我们将搜索范围缩小到右半部分，即 low = mid + 1。

3. 详细步骤

   • 步骤1：初始化
     定义两个指针，low 指向数组起始索引 0，high 指向数组末尾索引 nums.length - 1。

   • 步骤2：循环二分
     当 low 小于 high 时，执行循环：

     1. 计算中间索引 mid = low + (high - low) / 2。这样写是为了防止 (low + high) 可能出现的整数溢出。
     2. 将中间值 nums[mid] 与右边界值 nums[high] 进行比较：
        • 情况A：如果 nums[mid] < nums[high]，则最小值在左半部分，包含 mid。执行 high = mid。
        • 情况B：如果 nums[mid] > nums[high]，则最小值在右半部分，不包含 mid。执行 low = mid + 1。
          （注意：由于题目假设无重复元素，所以不会出现 nums[mid] == nums[high] 的情况。如果存在重复元素，此方法需要调整。）

   • 步骤3：返回结果
     当循环结束时，low 和 high 会指向同一个元素，这个元素就是数组中的最小值。返回 nums[low] 或 nums[high]。

4. 举例说明
   以题目中的例子 nums = [4, 5, 6, 7, 0, 1, 2] 为例：

   • 初始状态：low = 0, high = 6。
   • 第一次循环：
     • mid = 0 + (6-0)/2 = 3。nums[mid] = 7, nums[high] = 2。
     • 7 > 2，属于情况B。最小值在右侧，low = mid + 1 = 4。
   • 当前范围：[4, 6]，即子数组 [0, 1, 2]。
   • 第二次循环：
     • low = 4, high = 6。mid = 4 + (6-4)/2 = 5。nums[mid] = 1, nums[high] = 2。
     • 1 < 2，属于情况A。最小值在左侧，包含 mid，high = mid = 5。
   • 当前范围：[4, 5]，即子数组 [0, 1]。
   • 第三次循环：
     • low = 4, high = 5。mid = 4 + (5-4)/2 = 4。nums[mid] = 0, nums[high] = 1。
     • 0 < 1，属于情况A。最小值在左侧，包含 mid，high = mid = 4。
   • 循环结束：此时 low (4) == high (4)，循环条件不满足。返回 nums[4] = 0，正确。

5. 边界情况处理

   • 数组未旋转：例如 nums = [1, 2, 3]。算法依然有效，因为每次比较 nums[mid] 都小于 nums[high]，会不断将 high 向左移动，最终 low 和 high 会停在索引 0，即最小值 1。
   • 单元素数组：例如 nums = [5]。初始 low = 0, high = 0，不进入循环，直接返回 nums[0]。

6. 代码实现（Java）

   public int findMin(int[] nums) {
       int low = 0;
       int high = nums.length - 1;
   
       while (low < high) {
           int mid = low + (high - low) / 2;
           if (nums[mid] < nums[high]) {
               // 最小值在左半部分，包括mid
               high = mid;
           } else {
               // 最小值在右半部分，不包括mid
               low = mid + 1;
           }
       }
       // 循环结束时，low == high，指向最小值
       return nums[low];
   }
   

总结：这道题是二分查找算法的一个经典变体。其核心在于利用旋转数组的特性，通过比较中间元素与右边界元素，来准确地判断最小元素所在的半区，从而将时间复杂度从 O(n) 优化到 O(log n)。理解 nums[mid] 与 nums[high] 比较的逻辑是掌握此题的关键。