⭐️题目来源

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如，数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一个旋转，该数组的最小值为1。

示例 1：

输入：[3,4,5,1,2]
输出：1

示例 2：

输入：[2,2,2,0,1]
输出：0

分析

刚开始看这个旋转数组的时候有点模糊，仔细想了想，我的解释如下：

数组刚开始是有序的，但可能有重复的数字

接着按任意点将其旋转，旋转过后数组就变成有序的两个部分，但从哪里开始旋转是任意的

因此这种要旋转一遍的数组就是旋转排序数组

题目要求：找到这种旋转数组当中最小的数字

方法一:暴力求解法（执行用时：0 ms 内存消耗：5.5 MB）

算法

1.从下标为0的元素开始遍历

2．每次进行比较，如果当前元素比相邻的下一个元素大，则对应的下一元素即为最小值.如果查到最后一个元素都没有出现这种情况，则下标为0的元素为最小元素(因为此时说明数组中有重复的元素)

int minArray(int* numbers, int numbersSize){
            int i,j;
            int min=numbers[0];
            for(i=0;i<numbersSize;i++)
            {
                if(min>numbers[i])
                {
                    min=numbers[i];
                }
            }
            return min;
}

方法二:二分法（执行用时：0 ms 内存消耗：5.5 MB）

一般二分查找的过程介绍

1．找到中间的关键字

2.比较查找的关键字与中间关键字的大小关系

3．如果相等就相当于已经找到

4．如果查找的关键字小于中间的关键字则在前半部分进行同样的过程（从小到大存储)

5．如果查找的关键字大于中间的关键字则在后半部分进行同样的过程（从小到大存储)

一般二分查找的要求

1.顺序存储

2.元素有序

原因

1．通过下标即可得到关键字

2．任取一个关键字的值即可确定所寻找关键字是在它前面还是后面

算法

1.从下标为0的元素开始遍历

2．每次进行比较，如果当前元素比相邻的下一个元素大，则对应的下一元素即为最小值.如果查到最后一个元素都没有出现这种情况，则下标为0的元素为最小元素(因为此时说明数组中有重复的元素)

情况一：当没有重复数字的时候

如果numbers[mid]>numbers[right],则前半部分一定是顺序的，最小值(分界点)在mid后面

因此我们就可以缩小查找范围，直接到mid后面找最小的元素

如果numbers[mid]<numbers[right],则后半部分一定是顺序的，最小值(分界点)在mid前面

因此我们就可以缩小查找范围，直接到mid前面找最小的元素

情况二：当有重复数字的时候

会出现numbers[mid]== numbers[right]的情况

此时我们并不能确定到底分界点出现在mid的前面还是后面

解决方法：暴力地从右到左进行遍历，知道mid指针的元素小于right指针的元素

int minArray(int* numbers, int numbersSize){
        int left=0,right=numbersSize-1,mid;
        while(left<right)
        {
            mid=left+(right-left)/2;
            if(numbers[mid]<numbers[right])
            {
                right=mid;
            }
            else if(numbers[mid]>numbers[right])
            {
                left=mid+1;
            }
            else
            {
                right--;
            }
        }
        return numbers[left];
}