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

---

一个已按升序排列的数组，被循环旋转了若干次，现在要找到其最小值。第一观测题目中的例子，因为数组是按升序排列的，但是旋转的分界点（7,0）却是降序，所以我们可以遍历数组，找到这个分界点，那么小的数就是最小值。为了防止旋转之后和未旋转是一样的，预先设置结果为第一个元素。代码如下：

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

本代码提交AC，用时3MS。

但是这个代码的最坏复杂度是O(n)的，和一个乱序的数组求最小值遍历一次的复杂度是一样的，本解法并没有利用到数组是已排序这个特点。
要想达到比O(n)更好的复杂度，自然的思路是二分查找的O(lgn)。数组4,5,6,7,0,1,2，中间元素为7，7>2，说明旋转分界点在右半部分，令l=mid+1，此时数组变为0,1,2，中间元素为1，1<2，说明右半部分是正常的，令r=mid。如此循环，直到不满足l<r。完整代码如下：

class Solution {
  public: int findMin(vector < int > & nums) {
    int l = 0, r = nums.size()– 1;
    while (l < r) {
      int mid = (l + r) / 2;
      if (nums[mid] > nums[r]) l = mid + 1;
      else r = mid;
    }
    return nums[l];
  }
};

本代码提交AC，用时3MS。

三刷。二分的代码其实很难写得bug free，尤其是上面的代码和正常的二分搜索不太一样。实际上，我们依然可以套用常规二分的方法，只不过需要做两点改动：

1. 更新l或r时，只更新为mid，而不是mid+1或者mid-1。常规二分搜索是要找target，所以当target!=nums[mid]时，可以直接跳过mid，到mid+1或者mid-1，但是这里需要找最小值，那么，mid就有可能是最小值，所以不能把mid跳过。
2. 不跳过mid又可能出现死循环的问题，比如[3,1,2]，nums[mid]<nums[r]，所以r=mid，之后的循环中l和mid都一直等于0，出现死循环。解决的办法也很简单，当r-l<=1时，说明此时最多只有两个数字，简单取min就可以得到最小值了。

这种修改方法解释起来逻辑很清楚，也很容易记忆，完整代码如下：

class Solution {
public:
	int findMin(vector<int>& nums) {
		int l = 0, r = nums.size() - 1;
		int ans = nums[0];
		while (l <= r) {
			if (r - l <= 1) {
				return min(nums[l], nums[r]);
			}
			int mid = l + (r - l) / 2;
			if (nums[mid] > nums[r]) {
				l = mid;
			}
			else {
				r = mid;
			}
		}
		return nums[l];
	}
};

本代码提交AC，用时0MS。

四刷。上述解法还是有点怪，为什么是比较nums[mid]和nums[r]呢，而不是比较nums[mid]和nums[l]呢？后者是否可行，事实上是可行的。

基本思想：如果数组没有旋转，则应该满足nums[l]<nums[m]<nums[r]。上述思路是，如果数组选择了，则找到的m可能不满足上述条件，如果不满足nums[m]<nums[r]，即上述if(nums[mid]>nums[r])，说明右半部分违反顺序，最小值应该在右半部分l=mid。这种解法是找违反顺序的，然后在违反顺序的区间进一步查找。

另一种思路是，找不违反顺序的，比如如果满足nums[l]<nums[r]，则说明左半部分满足顺序，所以最小值应该在右边，同样有l=mid。但是这里有一个问题，就是如果数组旋转之后和没旋转是一样的，比如是[1,2,3]，则左边没违反顺序，在右边找最小值，只能找到2，答案错误。所以需要在开头加一个判断，即如果数组头<尾，则说明数组旋转前后是一样的，直接输出头元素为最小值。完整代码如下：

class Solution {
public:
    int findMin(vector<int>& numbers)
    {
        int n = numbers.size();
        int l = 0, r = n - 1;
        if (numbers[l] < numbers[r])
            return numbers[l]; // 注意这一句
        while (l <= r) {
            if (r - l <= 1)
                return min(numbers[l], numbers[r]);
            int m = l + (r - l) / 2;
            if (numbers[l] < numbers[m]) { // 左边有序，在右边找
                l = m;
            }
            else { // 左边无序，在左边找
                r = m;
            }
        }
        return 0;
    }
};

本代码提交AC，用时4MS。