常见算法题总结（旋转数组的最小数字）

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

方法1：很简单，直接全部扫描一遍。时间复杂度为O（n）。没有利用到题目中的特性。不可取。

方法2：在一定程度上是有序的，可以尝试用一下二分法。要注意特殊情况，如：{2,2,2,0,2}、{10,10,0,10,10}、{1,3}。{1，3，5}等情况。时间复杂度可达到O(logn)

Java代码如下：

 public static int getMin(int[] arr){
        int begin = 0;
        int end = arr.length-1;
        int mid = (begin+end)/2;
        //本身是有序的就不要比了
        if (arr[end] > arr[begin]){
            return arr[begin];
        }
        while ( begin+1 < end){
            //begin+1后，再检查一遍后面的是否为有序的，针对特殊情况的
            if (arr[end] > arr[begin]){
                return arr[begin];
            }
            //中间那个数在前面的那个有序数组中
            if (arr[begin] < arr[mid]){
                begin = mid;
            //中间那个数在后面的那个有序数组中
            }else if (arr[begin] > arr[mid] ){
                end = mid;
            }else {//有重复的数的时候
                begin+=1;
            }
            mid = (begin + end)/2;
        }
        return arr[end];
    }