189 8069 5689

输出一个为递增排序数组的旋转数组中的最小元素——8

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

网站制作、网站设计的关注点不是能为您做些什么网站，而是怎么做网站，有没有做好网站，给成都创新互联一个展示的机会来证明自己，这并不会花费您太多时间，或许会给您带来新的灵感和惊喜。面向用户友好，注重用户体验，一切以用户为中心。

    当然了，将数组遍历一遍肯定能找出最小值，但其时间复杂度为O(N)，效率是最低的，因此，应该有一种更高效的解决办法。

    

    因为原数组是递增的，因此数组的第一个元素一定是最小值，而旋转之后，其最小值就会成为旋转的分界点，因此，查找一个旋转之后数组的最小值可以变成查找一个旋转数组的旋转点。而我们仍然可以发现，在旋转点之前的序列是递增有序的，而在旋转点之后的序列也是递增有序的，因此可以这样判断：

  1. 取数组的中间值；

  2. 如果中间值比最左值大且比最右值小，那么这个数组就是递增数组旋转幅度为0，最小值就为数组第一个值，直接返回；

  3. 如果中间值比左边一个数小且比右边一个数小，那么中间值就为旋转点也就是最小值，直接返回；

  4. 如果中间值比最左值大且比最右值大，那么中间值往左一定是递增有序的，而旋转点一定在中间值往右，将范围缩到中间值右半边重新从第1步开始；

  5. 如果中间值比最左值小且比最右值小，那么中间值往右一定是递增有序的，而旋转点一定在中间值往左，将范围缩到中间值左半边重新从第1步开始；

    上面的分析其实是相当于在用二分查找来做，这样就将时间复杂度降为了O(lgN),下面用代码来实现：

#include 
#include 
using namespace std;

int find_min_num(const int *arr, size_t n)
{
    assert(arr && n); 

    int left = 0;
    int right = n-1;
    int mid = (right-left)/2;

    while(left < right)
    {   
        if((arr[left] <= arr[mid]) && (arr[mid] <= arr[right]))
        {
            break;//当数组区间为递增时，最小值就为最左值
        }
        else if((arr[mid-1] > arr[mid]) && (arr[mid+1] > arr[mid]))
        {
            return arr[mid];//当取到的中间值就为旋转点时，最小值就为中间值
        }
        else if((arr[left] <= arr[mid]) && (arr[mid] >= arr[right]))
        {
            left = mid + 1;//当中间值比左边大且比右边大时
        }
        else
        {
            right = mid - 1;//除去上面的三种情况就只剩一种了，那就是中间值比左线小且比右边小
        }

        mid = (right-left)/2 + left;
    }   
    return arr[left];
}

int main()
{
    int arr[] = {8, 9, 2, 3, 4, 5, 6, 7};
    
    int ret = find_min_num(arr, sizeof(arr)/sizeof(arr[0]));
    cout<<"the min number is: "<
运行程序，输出结果为2；
输出一个为递增排序数组的旋转数组中的最小元素——8
可以将数组设定为不同的情况来检验。
《完》
            
            
                        

            网页标题：输出一个为递增排序数组的旋转数组中的最小元素——8            

            网页地址：http://jkwzsj.com/article/gjchcs.html

其他资讯