[查找和排序]旋转数组的最小数字

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

以自然数举例

num[]：第一行表示索引，下方表示对应的值（上下位置表示的是数字大小关系）
0 1 2 3 4 5 6 7 8
| | | | | | | | 9
| | | | | | | 8
| | | | | | 7
| | | | | 6
| | | | 5
| | | 4
| | 3
| 2
1  

随意旋转一下数组，可能会得到这样的结果

num[]：第一行表示索引，下方表示对应的值（上下位置表示的是数字大小关系）
0 1 2 3 4 5 6 7 8
| | | 9 | | | | |
| | 8   | | | | |
| 7     | | | | |
6       | | | | |
        | | | | 5
        | | | 4
        | | 3
        | 2
        1

假设原数组是严格单增的（后续会提到若存在不严格单增如何处理）
那么旋转后数组应该就像事例中结果，存在两个单增的子序列。
假设一个数字x，x ≥ num[0]，那么说明x在第一段子序列中
假设x ≤ num[n - 1]，那么说明x在第二段子序列中

采用二分查找的方法，首先二分的两头为[0,n-1]
找到中间值mid，mid作为索引所对应的值num[mid]假如在第一段子序列中，说明左指针仍然有右移空间。反之说明右指针有左移空间
二分找到值骤减的连续两项，后一项即为所求的最小数字

这道题是不严格单增的，即可能出现等值情况。这个时候我们没有办法，只能用暴力法寻找最小值。一个例子为

索引     0 1 2 3 4 5 6 7 8 9
数组     1 1 1 0 1 1 1 1 1 1
一次二分          1 1 1 1 1 1

显然二分时丢失了部分可能的最小值

具体代码：

import java.util.ArrayList;
public class Solution {
    public int minNumberInRotateArray(int [] array) {
        if(array.length == 0){
            return 0;//因传入参数而导致题目无意义
        }
        /*初值设定
        * left : 数组起始索引 0
        * right: 数组尾部索引 n - 1
        * mid  : 中间值索引
        */
        int left = 0;
        int right = array.length - 1;
        int mid = (left + right ) / 2;
        
        //只有left值 > right值，二分才有意义
        //等于时，需要暴力查找
        while(array[left] > array[right]){
            //假设left和right已经只相差1了，说明已经找到了。
            //此时left指向最大值，right指向最小值
            //由于while条件不取等，所以不会出现left = right情况
            if(left == right - 1){
                mid = right;
                break;
            }
            //找到中间索引值
            mid = (left + right) / 2;
            //mid在第一段非减区间
            if(array[left] <= array[mid]){
                left = mid;
            }
            //mid在第二段非减区间
            else{
                right = mid;
            }
        }
        //左右侧相等时，暴力搜索
        if(array[left] == array[right]){
            for(int i = left; i < right; i++){
                //mid锁定最小array值位置
                mid = (array[mid] < array[i])? mid : i;
            }
        }
        return array[mid];
    }
}