Leetcode153 Find Minimum in Rota

记忆点

• 二分查找
• 头尾比较

思路

使用中间点的数值，根据其与第一个元素和末尾元素的大小关系，判断最小值是在中间点的左边或者右边，进行二分查找
令人印象深刻的点是，比较的过程中对于等于情况的处理，涉及到边界条件：

1. 在旋转非零个元素的情况下 数组可以拆分成两个递增数组。如果，说明属于第一个数组；如果，说明属于第二个数组；通过不断地确定第一个数组和第二个数组的元素，得到与第一个数组毗邻的属于第二个数组的元素，恰好就是最小元素
2. 旋转零个元素 此时，最小元素是
3. 特殊情况：数组非严格递增数列 只能线性排查，二分失效，以下两张示意图分别展示了中点属于第二个数组，以及属于第一个数组的两种情况：
   

实现

class Solution {
public:
    int findMin(vector<int>& nums) {
        if (nums.size() == 1) return nums[0];
        
        int head = 0, tail = nums.size() - 1;
        int mid = head;
        
        // 由于size > 1，第一次比较在严格递增情况下不会相等，之后也不会，故大于即可
        while (nums[head] > nums[tail]) {
            if (head == tail - 1) {
                mid = tail;
                break;
            }
            
            mid = (head + tail) / 2;
            // mid属于第一个数组
            if (nums[mid] >= nums[head]) {
                head = mid;
            }
            // mid属于第二个数组
            else if (nums[mid] <= nums[tail]) {
                tail = mid;
            }
        }
        
        return nums[mid];
    }
};