11-旋转数组的最小数字

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

第一种：

无脑遍历，依次比较，找到最小值。这种方法对于任意的数组都是可行的，题目中给定的条件是一个递增数组的旋转，这个条件并没有利用上。

public int findMin(int[] arr){
    int min = arr[0];
  	for (int i = 1; i < arr.length; i++) {
      if (min > arr[i]) {
           min = arr[i];
      }
  	}
  return min;
}
java8样式:
 int findMin(int[] numbers) {
        return Arrays.stream(numbers).min().getAsInt();
 }

第二种：

考虑旋转数组的特性，比如 3 4 5 1 2，如下图所示，我们直接遍历数组，如果后一个元素比前一个小，则后面的这个元素就是最小值。其中需要注意1 2 3 4 5这种特殊情况。

public int minNumberInRotateArray(int [] array) {
        if (array == null) {
            return 0;
        }
        if (array.length == 1) {
            return array[0];
        }
        for (int i = 0; i < array.length - 1; i++) {
            if (array[i] > array[i + 1]) {
                return array[i+1];
            }
        }
        return array[0];
    }

第三种:

二分法

1 严格递增数组

以 3 4 5 1 2 为例，我们观察就可以知道，前半部分是 3 4 5 ，后半部分是 1 2 。 按照旋转数组的定义，前半部分的最小值大于后半部分的最大值，我们考虑使用二分法如何处理。

   public int minArray(int[] arr) {
        if (arr == null) {
            return -1;
        }
        int lo = 0;
        int hi = arr.length;
        //循环终止条件是lo==hi，这样最后不用考虑是用lo还是用hi
        while (lo < hi) {
            int mid = (lo + hi) >>> 1;
            if (arr[mid] > arr[0]) {
               //如果中间元素较大，说明mid还处于前半部分的上升阶段，即类似于 3 4 5上升阶段，最小值肯定不是mid，所以用lo=mid+1
                lo = mid + 1;
            }else if(arr[mid] < arr[0]){
              //如果中间元素较小，说明mid处于后半部分的上升阶段，类似于 1 2这段。这就说明最小元素一定在左边，那么我们需要左移hi，不断的缩小空间。同时因为最小值有可能是mid，所以不能用hi=mid-1，需要用hi=mid。
                hi = mid;
            }else{
               //如果出现了相等的元素，说明不是严格递增的数组，那么就只能遍历查找了，这里注意，需要直接查找整个数组。           
              return findMin(arr);
            }
        }
        //最后检查下，如果lo越界了，说明是类似于 1 2 3 4 5这样的递增的数组，最小的即是arr[0]
        if(lo == arr.length){
            return arr[0];
        }
        return arr[lo];
    }

    public int findMin(int[] arr) {
        return Arrays.stream(arr).min().getAsInt();
    }

2 非严格递增数组

对于 0 1 1 1 1 这种非严格递增的数组 ，需要在二分法时特殊处理，即遇到相等的元素时直接顺序查找。在上面的二分程序中兼容即可。