153. 寻找旋转排序数组中的最小值（二分套路）

https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array/
这个题目，元素是unique的。难度并不高，二分细节难搞，没关系，咱们记住套路。
154是个hard, 元素是可以重复的，先不做。先把这个题套路记住了。

分三种情况：
1） 1 2 3 4 5
无旋转，最小值在左，左<中<右，收缩右边界。

2. 4 5 1 2 3
   有旋转，最小值在左，左>中，中<右，收缩右边界。（中可能是最小）
   3） 2 3 4 5 1
   有旋转，最小值在右，左<中，中>右，收缩左边界。（中不可能是最小）

分析前面三种可能的情况，会发现情况1、2是一类，情况3是另一类。

如果中值 < 右值，则最小值在左半边，可以收缩右边界。
如果中值 > 右值，则最小值在右半边，可以收缩左边界。

class Solution {
public:
    int findMin(vector<int>& nums) {
        int left = 0, right = nums.size() - 1;
        while (left < right) {
            int mid = left + (right - left) / 2; /* 地板除，mid更靠近left */
            if (nums[mid] < nums[right]) {
                right = mid; /* 因为中值 < 右值，中值也可能是最小值，右边界只能取到mid处 */ 
            } else {
                left = mid + 1; /* 因为中值 > 右值，中值肯定不是最小值，左边界可以跨过mid */
            }
        }
        return nums[left]; /* 循环结束，left == right，最小值输出nums[left]或nums[right]均可 */   
    }
}

按照这个模板，记住就好！以上分析都是为了辅助记忆！

二分套路总结：
https://leetcode-cn.com/problems/search-insert-position/solution/te-bie-hao-yong-de-er-fen-cha-fa-fa-mo-ban-python-/