Leetcode题解剑指 Offer 11. 旋转数组的最小数字

PROBLEM

难度简单

MY ANSWER

二分法，交了好几次改的代码很乱。时间复杂度O(log n)，空间复杂度O(1)。

class Solution {
public:
    int minArray(vector<int>& numbers) {
        int min = 0;
        int x = numbers.size();
        int l = 0, r = numbers.size() - 1;
        if(x == 1) {
            return numbers[0]; 
        }
        while(x) {
            int mid = (l + r) / 2;
            if(mid == l) {
                break;
            }
            if(numbers[l] == numbers[mid] && numbers[l] == numbers[mid]) {
                l++;
                continue;
            }
            if(numbers[l] <= numbers[mid] && numbers[mid] <= numbers[r]) {
                return numbers[l];
            }
            if(numbers[l] <= numbers[mid]) {
                l = mid;
            }
            else {
                r = mid;
            }
        }
        return numbers[l] < numbers[r] ? numbers[l] : numbers[r];
    }
};

BETTER SOLUTION

同样二分法，代码更简洁易懂，使用low + (high - low) / 2可以防止high+low溢出。high与pivot比较可以避免数组只有两个元素时，pivot和low相等。low = pivot + 1，避免只有两个数的死循环。两数相同时，high减少至不相等后继续二分。

class Solution {
public:
    int minArray(vector<int>& numbers) {
        int low = 0;
        int high = numbers.size() - 1;
        while (low < high) {
            int pivot = low + (high - low) / 2;
            if (numbers[pivot] < numbers[high]) {
                high = pivot;
            }
            else if (numbers[pivot] > numbers[high]) {
                low = pivot + 1;
            }
            else {
                high -= 1;
            }
        }
        return numbers[low];
    }
};

SUMMARY

二分法常考，注意其代码的实现细节。