LeetCode 153.寻找旋转排序数组中的最小值

题目描述

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

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

请找出其中最小的元素。

你可以假设数组中不存在重复元素。

示例 1:

输入: [3,4,5,1,2]
输出: 1

示例 2:

输入: [4,5,6,7,0,1,2]
输出: 0

解法思路

直观方法：从左到右遍历，遇到一个元素比它左右都小，就是所找的答案（需要注意没有经过旋转和在最小值在末尾的情况）。

优化：二分搜索

代码如下：

class Solution {
public:
    int findMin(vector<int>& nums) {
        if (nums.size() == 1) {
            return nums[0];
        }

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

        if (nums[right] > nums[0])
            return nums[0];

        while (left < right) {
            int mid = (left + right) / 2;

            if (nums[mid] > nums[mid + 1])
                return nums[mid + 1];

            if (nums[mid] < nums[mid - 1])
                return nums[mid];

            if (nums[mid] > nums[0])
                left = mid + 1;
            else
                right = mid - 1;
        }

        return -1;
    }

附：暴力的直观方法代码

int findMin2(vector<int>& nums) {
        if (nums.size() == 1) {
            return nums[0];
        }
        if (nums[nums.size() - 1] < nums[nums.size() - 2])   // 最小值在末尾
            return nums[nums.size() - 1];

        if (nums[nums.size() - 1] > nums[0]) // 没有经过旋转
            return nums[0];

        for (int i = 1; i < nums.size() - 1; ++i) {
            if (nums[i] < nums[i - 1] && nums[i] < nums[i + 1])
                return nums[i];
        }

        return -1;
    }

在LeetCode的测试集下，两种方法相差4ms