题目

假设按照升序排序的数组在预先未知的某个点上进行了旋转。

( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。

请找出其中最小的元素。

注意数组中可能存在重复的元素。

示例 1：

输入: [1,3,5]
输出: 1
示例 2：

输入: [2,2,2,0,1]
输出: 0

题解（使用二分法）

• 题目可以理解为：寻找旋转数组的最小元素即为寻找右排序数组的首个元素
• 循环二分
  • 当 numbers[mid] > numbers[j]时： mid一定在 右排序数组 中，即旋转点 x 一定在 [mid+ 1, j] 闭区间内，因此执行 i = mid+ 1；
  • 当 numbers[mid] < numbers[j] 时： mid一定在 左排序数组 中，即旋转点 x 一定在[i, mid]闭区间内，因此执行 j = mid；
  • 当 numbers[mid] == numbers[j] 时： 无法判断 mid在哪个排序数组中，即无法判断旋转点 x 在 [i, mid] 还是 [mid+1,j] 区间中。解决方案： 执行j=j−1 缩小判断范围
• 当 i = ji=j 时跳出二分循环，并返回 numbers[i] 即可

代码

  public int MinArray(int[] numbers)
    {
        int i = 0;
        int j = numbers.Length - 1;
        while (i<j)
        {
            int m = (i + j) / 2;
            if (numbers[m] > numbers[j]) i = m + 1;
            else if (numbers[m] < numbers[j]) j = m;
            else --j;//如果是不存在重复元素，则不需要此步骤
        }
        return numbers[i];
    }