旋转数组的最小数字

---

题目：

题解：

1、使用二分法+暴力

• 解题思路：寻找旋转数组的最小元素即为寻找 右排序数组 的首个元素 nums[x] ，称 x为 旋转点 。

  • 
  • 
  • 
  • 
  • 
  • 
  • 
  • 
  • 
  • 

• 复杂度分析：

  • 时间复杂度 O(log_2 N) ： 在特例情况下（例如 [1, 1, 1, 1]），会退化到 O(N)。
  • 空间复杂度 O(1)： i , j , mid 变量使用常数大小的额外空间。

• 代码：

  // 二分法求解
  class Solution {
      public int minArray(int[] numbers) {
          int i = 0;
          int j = numbers.length - 1;
          while(i < j) {
              int mid = i + (j-i) / 2;
              if (numbers[mid] < numbers[j]) {
                  j = mid;
              }else if (numbers[mid] > numbers[j]) {
                  i = mid + 1;
              }else j--;
          }
          return numbers[i];
      }
  }

• 补充思考： 为什么本题二分法不用 nums[mid] 和 nums[i] 作比较？

  ​ 二分目的是判断 mid 在哪个排序数组中，从而缩小区间。而在 nums[m] > nums[i]情况下，无法判断 mid 在哪个排序数组中。本质上是由于 j 初始值肯定在右排序数组中； i 初始值无法确定在哪个排序数组中。举例如下：

  对于以下两示例，当 i = 0, j = 4, mid = 2 时，有 nums[m] > nums[i] ，而结果不同。

  [1, 2, 3, 4 ,5] 旋转点 x = 0 ： m 在右排序数组（此示例只有右排序数组）；

  [3, 4, 5, 1 ,2] 旋转点 x = 3 ： m 在左排序数组。