题解 | #旋转数组的最小数字#

方法：二分法

题设中的条件：非降序的数组进行旋转。非降序说明数组是升序数组且可能有重复元素。

通过观察可以得到：对于一个非降序的数组，取数组的中间元素与数组最右边的元素进行比较，如果中间元素大于最右边元素，最小值一定在中点右侧（不包括中点）；如果中间元素小于最右边元素，最小值一定在中点左侧（包括中点）；如果中间元素等于最右边元素，这时无法判断在哪一侧，但是可以将最右侧元素筛除掉。

时间复杂度：o(logⁿ)

空间复杂度：o(1)

class Solution {
  public:
    int minNumberInRotateArray(vector<int>& nums) {
        //特殊情况处理
        if (nums.size() == 1)
            return nums[0];

        int left = 0;
        int right = nums.size() - 1;
        int mid;

        while (left <= right) {
            mid = (left + right) / 2;
            //中点大于最右侧时，最小值一定在中点右侧
            if (nums[mid] > nums[right])
                left = mid + 1;
            //中点小于最右侧时，最小值可能为中点或者在中点的左侧
            else if (nums[mid] < nums[right])
                right = mid;
            //中点等于最右侧时，无法判断在哪一侧
            else
                right--;
        }
        return nums[mid];
    }
};