LeetCode: Find Minimum in Rotated Sorted Array I && II

思路分析

跟“Search in Rotated Sorted Array”本质上是一类问题，同样期望O(log(n))的算法复杂度。核心思想稍微简单一些：如果num[mid]落在了区间1，则num[low]是当前可见的最小值，用它更新答案，然后在[mid+1, high)区间中继续寻找；否则，那么num[mid]是当前可见的值，虽然不一定是最小，但是没有什么有效的方法可以保证能找到更小，因此先用它更新答案后，再在[low, mid)区间中继续寻找。

注意，在二分查找中，如果出现low==high-1的情况，则此时mid==low，那么就需要注意如何处理以脱离死循环。

另外，对于允许重复元素的情形，还是不得不在更新最小值后将左指针右移一位，以尝试脱离存在重复元素的区域，导致算法复杂度降低为O(n)。

代码

第一问

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

第二问

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