[leetcode]Find Minimum in Rotated Sorted Array II

1419 ワード

二分、いろいろな状況.
class Solution {

public:

    int findMin(vector<int> &num) {

        int size = num.size();

        int minVal = num[size-1];

        findMinRe(num, 0, size - 1, minVal);

        return minVal;

    }

    

    void findMinRe(vector<int> &num, int left, int right, int &minVal) {

        if (right < left) return;

        int mid = (left + right) / 2;

        if (num[left] < num[right]) {

            minVal = min(minVal, num[left]);

            return;

        }

        if (num[left] > num[right]) {

            minVal = min(minVal, num[right]);

            if (num[mid] <= num[right]) {

                minVal = min(minVal, num[mid]);

                findMinRe(num, left, mid - 1, minVal);

            } else {

                findMinRe(num, mid + 1, right, minVal);

            }

        }

        if (num[left] == num[right]) {

            minVal = min(num[left], minVal);

            if (num[mid] < num[right]) {

                minVal = min(minVal, num[mid]);

                findMinRe(num, left, mid - 1, minVal);

            } else if (num[mid] > num[right]) {

                findMinRe(num, mid + 1, right, minVal);

            } else { // ==

                findMinRe(num, left, mid - 1, minVal);

                findMinRe(num, mid + 1, right, minVal);

            }

        }

    }

};