C++题解 | #旋转数组的最小数字#

题目本身暴力法遍历数组即可求解，但其时间复杂度相对而言较大，且根据旋转数组的特点，可知时间复杂度还有减小的余地，即主体采用二分法。特殊情况，则专门考虑遍历。
整体程序虽增多，但其时间复杂度却降低了。

class Solution {
public:
    int minNumberInRotateArray(vector<int> rotateArray) {
        /*int n = rotateArray.size();
        int i = 0, j = 0;
        for (i = 0; i <= n - 2; i++) {
            j = i + 1;
            if (rotateArray[i] > rotateArray[j]) {
                break;
            }
        }
        if (i == n - 1)
        return rotateArray[0];
    else
        return rotateArray[j];*/
        int n = rotateArray.size();
        int i = 0, j = n - 1, mid;
        if (rotateArray[i] < rotateArray[j])
            return rotateArray[i];
        while (i <= j) {
            if (j - i == 1) {
                mid = j;
                break;
            }
            mid = i + (j - i) / 2;
            if (rotateArray[i] == rotateArray[mid] && rotateArray[mid] == rotateArray[j])
                return Minrott(rotateArray); //特殊情况专门遍历
            if (rotateArray[mid] >= rotateArray[i])
                i = mid;
            else
                j = mid; 
        }
        return rotateArray[mid];
    }
    int Minrott(vector<int> rotateArray) {
        int n = rotateArray.size(), j;
        for (int i = 0; i < n - 1; i++) {
            j = i + 1;
            if (rotateArray[i] > rotateArray[j])
                break;
        }
        return rotateArray[j];
    }
};