LeetCode: 153. Find Minimum in Rotated Sorted Array

题目描述

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.
(i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]).

Find the minimum element.

You may assume no duplicate exists in the array.

Example 1:

Input: [3,4,5,1,2] 
Output: 1

Example 2:

Input: [4,5,6,7,0,1,2]
Output: 0

解题思路

由于没有相同的数字出现，因此可能出现的情况有以下几种：

没有翻转数字，如：[0，1，2，3，4，5]。这种情况最小数字在最前面、
翻转数字后，中间数字在最小数字前，如：[2, 3, 4, 5, 0, 1]。这种情况最小数字在中间数字后面的区间。
翻转数字后，中间数字在最小数字后，如：[4, 5, 0, 1, 2, 3]。这种情况最小数字在中间数字前面的区间。

AC 代码

class Solution {
public:
    // [beg, end)
    int findMinRef(const vector<int>& nums, int beg, int end)
    {
        if(beg >= end) return INT_MAX;
        if(beg + 1 == end) return nums[beg];

        int mid = (beg+end)/2;

        // 0 1 2 3 4 5 类型， mid = (0+6)/2 = 3
        if(nums[beg] <= nums[mid] && nums[mid] <= nums[end-1])
        {
            return nums[beg];
        }
        // 4 5 0 1 2 3 类型, mid = (0+6)/2 = 3
        else if(nums[beg] > nums[mid] && nums[mid] <= nums[end-1])
        {
            if(nums[mid] == nums[end-1]) return nums[mid];
            return findMinRef(nums, beg, mid+1);
        }
        // 2 3 4 5 0 1， mid = (0+6)/2=3
        else if(nums[beg] < nums[mid] && nums[mid] >= nums[end-1])
        {
            if(nums[mid] == nums[end-1]) return nums[beg];
            return findMinRef(nums, mid, end);
        }
    }
    int findMin(vector<int>& nums) {
        return findMinRef(nums, 0, nums.size());
    }
};