By

文章目录

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

首先最简单的方法是扫一遍，复杂度O(n)，很明显没有用到数组递增的特性，肯定不是最好的啊。
仔细观察和分析一下，会发现，其实这就是两个递增的数组。并且，前一个数组的每一个元素都比后面的数组的大。所以可以想一下用二分的思想去解决。如果data[mid]>data[left]，说明该中点元素是第一个数组的，所以最小的是在后面，就可以舍弃前半段的搜索，否则，说明中间元素在后面的数组中，此时就可以去前面数组找。这样就可以用二分查找的方式找到最小的元素了。

但是要考虑特殊情况，就是没有元素转移到数组末尾，此时最小的元素就是第一个元素，所以还要和第一个元素取min,这才是最后的结果。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

int getmin(int a[],int length){

      int left=0,right=length-1;

    while (left<right){
        int mid = (left+right)/2;
        if(a[mid]>a[left]){
            left=mid+1;
        }
        else{
            right=mid;
        }
    }
    return min(a[0],a[left]);

}
文章目录