Ex11 旋转数组的最小数字

题目描述

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如，数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一个旋转，该数组的最小值为1。

题目分析

做这道题的基本方法就是二分搜索（也叫二分查找，Binary Search）。但是，要特别注意两种情况：

• 当数组只有一种数字时，如[1, 1, 1, 1, 1]；
• 当数组不旋转时，即旋转了0个元素时，如[1, 3, 5]。

这回先上代码。

代码

int minRange (int *numbers, int low, int high);

int
minArray (int *numbers, int numbersSize)
{
  if (!numbers || numbersSize <= 0)
    return 0;
  int low = 0, high = numbersSize - 1, mid = low;
  while (numbers[low] >= numbers[high])
    {
      if (high - low == 1)
        {
          mid = high;
          break;
        }
      mid = (high + low) / 2;
      if (numbers[high] == numbers[mid] && numbers[low] == numbers[mid])
        {
          return minRange (numbers, low, high);
        }
      if (numbers[low] <= numbers[mid])
        {
          low = mid;
        }
      else if (numbers[high] >= numbers[mid])
        {
          high = mid;
        }
    }
  return numbers[mid];
}

int
minRange (int *numbers, int low, int high)
{
  int res = numbers[low];
  for (int i = low + 1; i <= high; ++i)
    {
      if (res > numbers[i])
        res = numbers[i];
    }
  return res;
}

代码分析

1. 针对当数组只有一种数字时，不能用二分查找来有效解决，我们使用了minRange函数，很简单的一个遍历。

2. 针对当数组不旋转时，即旋转了0个元素时，我们使用了while (numbers[low] >= numbers[high])作为进入循环的条件。

   此处要注意的是：

   1. 我们使用mid元素作为返回值，因此，初始化的时候，将mid设为low，即index为0的时候。
   2. 一般情况下，mid可能初始为0，但如果在代码中不将mid赋值时，leetcode的AddressSanitizer会报错。

3. 另外要注意的是边界条件检查，特别是=号的位置。

4. 一个Tip：low/high/mid的赋值。

   int low = 0, high = numbersSize - 1, mid = (low + high) / 2;
   

结果

执行结果：通过

执行用时：8 ms, 在所有 C 提交中击败了47.26%的用户

内存消耗：5.6 MB, 在所有 C 提交中击败了82.33%的用户