JZ6 — 旋转数组的最小数字

题目描述

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。
输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。
例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。
NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。

题目分析

题目的表述有点不清楚，“非递减排序的数组”指的是除了递减数组之外的所有数组（包括乱序），还是指数组中的每个元素都不小于它的前一个元素？
这里的意思应该是第二种，即数组中的每个元素都不小于它的前一个元素。
对非递减数组进行旋转操作，要找出数组中的最小值。
直接遍历一下就解决了，时间复杂度为O(n)，但这样肯定不是最佳解决方法。

对于有序数据的查找，大家都知道要使用二分查找。那么这个问题是不是也可以使用二分的思想呢？
但我们会发现，取出中间位置mid对应的值后，不知道该和谁进行比较了，即缺少一个目标值target。
不妨就让右边界对应的值作为目标值target。
1. rotateArray[mid] > target时，说明mid和mid左边的值肯定不是最小值，因此可以令左边界left = mid + 1；
2. rotateArray[mid] < target时，说明mid右边的值肯定不是最小值，因此可以令右边界right = mid；
3. rotateArray[mid] == target时，说明rotateArray[mid]有可能是最小值（例如2 3 1 1 1），也有可能不是最小值（例如1 1 1 0 1），不过可以肯定的是，此时的右边界已经无用了，因此令右边界right--。

最终，当循环结束时，rotateArray[mid]就是答案。
当然，也可以让左边界对应的值作为目标值target，对应的判断方法做出相应改变即可。
综上所述，时间复杂度为O(log(n))，最坏为O(n)。

C++

class Solution
{
public:
    int minNumberInRotateArray(vector<int> rotateArray)
    {
        if (rotateArray.size() == 0)
            return 0;
        int left = 0, right = rotateArray.size() - 1, mid;
        while (left <= right)
        {
            mid = left + (right - left) / 2;
            int target = rotateArray[right];
            if (rotateArray[mid] > target)
                left = mid + 1;
            else if (rotateArray[mid] < target)
                right = mid;
            else
                right--;
        }
        return rotateArray[mid];
    }
};

Java

import java.util.ArrayList;
public class Solution {
    public int minNumberInRotateArray(int[] array) {
        if (array.length == 0)
            return 0;
        int left = 0, right = array.length - 1, mid = 0;
        while (left <= right) {
            mid = left + (right - left) / 2;
            int target = array[right];
            if (array[mid] > target)
                left = mid + 1;
            else if (array[mid] < target)
                right = mid;
            else
                right--;
        }
        return array[mid];
    }
}