[剑指Offer]11-旋转数组的最小数字（二分查找）

题目链接

https://www.nowcoder.com/practice/9f3231a991af4f55b95579b44b7a01ba?tpId=13&tqId=11159&tPage=1&rp=4&ru=%2Fta%2Fcoding-interviews&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking

题意

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。 输入一个非减排序的数组的一个旋转，输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。 NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。

解题思路

使用二分查找思想，可以将时间复杂度由O(n)优化到O(logn)。
旋转数组特点：

• 由左右两个有序数组组成，左边的数组元素都大于等于右边的数组元素，要找的最小元素是右边数组的第一个。
• 可以采用二分法，拿中间元素与左右两端元素比较，若大于等于l，则中间元素属于左数组，令l=mid；若小于等于r，则中间元素属于右数组，令r=mid。
• 最终，将l=r-1，而最小元素即为r所指元素，这是终止条件。

考虑特例：

• 特例1 左旋转为前0个，此时最小元素为第一个，要单独判断这种情况。
• 特例2 l r mid 三个指向的元素相同，此时无法判断mid要归在左边还是右边，进而影响最终的结果，所以这种情况只能使用顺序查找。

相关知识

二分查找的思考：我认为二分查找的关键是首先满足“有序”的条件，方法的精髓则是用数组中间的元素与某些东西比较，达到每次减少一半范围的效果，以将查找复杂度优化到O(logn)。

代码

class Solution {
public:
    int minNumberInRotateArray(vector<int> rotateArray) {
        if (rotateArray.size() == 0) {
            return 0;
        }
        else if (rotateArray.size() == 1) {
            return rotateArray[0];
        }
        else if (rotateArray.size() == 2) {
            return rotateArray[0] < rotateArray[1] ? rotateArray[0] : rotateArray[1];
        }
        else{
            size_t l = 0;
            size_t r = rotateArray.size() - 1;

            if (rotateArray[l] < rotateArray[r]) {//特例1 旋转左边0个
                return rotateArray[l];
            }

            size_t mid;
            while (l != r - 1) {
                mid = (l + r) / 2;
                if (rotateArray[l] == rotateArray[r] && mid == rotateArray[l]) {//特例2 三者相等，无法判断mid指向的元素属于左边的有序数组还是右边的有序数组，此时只能采用顺序查找
                    break;
                }
                if (rotateArray[mid] >= rotateArray[l]) {
                    l = mid;
                }
                else if (rotateArray[mid] <= rotateArray[r]) {
                    r = mid;
                }
            }

            if (l != r - 1) {//顺序查找
                int min = rotateArray[0];
                for (int i = 1;i < rotateArray.size();++i) {
                    if (rotateArray[i] < min) {
                        min = rotateArray[i];
                    }
                }
                return min;
            }
            else {
                return rotateArray[r];
            }
        }
    }
};

[剑指Offer]11-旋转数组的最小数字（二分查找）

原文：https://www.cnblogs.com/coding-gaga/p/10473889.html