把一個(gè)數(shù)組最開始的若干個(gè)元素搬到數(shù)組的末尾，我們稱之為數(shù)組的旋轉(zhuǎn)。 輸入一個(gè)非減排序的數(shù)組的一個(gè)旋轉(zhuǎn)，輸出旋轉(zhuǎn)數(shù)組的最小元素。 例如數(shù)組{3,4,5,1,2}為{1,2,3,4,5}的一個(gè)旋轉(zhuǎn)，該數(shù)組的最小值為1。 NOTE：給出的所有元素都大于0，若數(shù)組大小為0，請返回0。

以自然數(shù)舉例

num[]：第一行表示索引，下方表示對應(yīng)的值（上下位置表示的是數(shù)字大小關(guān)系）
0 1 2 3 4 5 6 7 8
| | | | | | | | 9
| | | | | | | 8
| | | | | | 7
| | | | | 6
| | | | 5
| | | 4
| | 3
| 2
1  

隨意旋轉(zhuǎn)一下數(shù)組，可能會得到這樣的結(jié)果

num[]：第一行表示索引，下方表示對應(yīng)的值（上下位置表示的是數(shù)字大小關(guān)系）
0 1 2 3 4 5 6 7 8
| | | 9 | | | | |
| | 8   | | | | |
| 7     | | | | |
6       | | | | |
        | | | | 5
        | | | 4
        | | 3
        | 2
        1

假設(shè)原數(shù)組是嚴(yán)格單增的（后續(xù)會提到若存在不嚴(yán)格單增如何處理）
那么旋轉(zhuǎn)后數(shù)組應(yīng)該就像事例中結(jié)果，存在兩個(gè)單增的子序列。
假設(shè)一個(gè)數(shù)字x，x ≥ num[0]，那么說明x在第一段子序列中
假設(shè)x ≤ num[n - 1]，那么說明x在第二段子序列中

采用二分查找的方法，首先二分的兩頭為[0,n-1]
找到中間值mid，mid作為索引所對應(yīng)的值num[mid]假如在第一段子序列中，說明左指針仍然有右移空間。反之說明右指針有左移空間
二分找到值驟減的連續(xù)兩項(xiàng)，后一項(xiàng)即為所求的最小數(shù)字

這道題是不嚴(yán)格單增的，即可能出現(xiàn)等值情況。這個(gè)時(shí)候我們沒有辦法，只能用暴力法尋找最小值。一個(gè)例子為

索引     0 1 2 3 4 5 6 7 8 9
數(shù)組     1 1 1 0 1 1 1 1 1 1
一次二分          1 1 1 1 1 1

顯然二分時(shí)丟失了部分可能的最小值

具體代碼：

import java.util.ArrayList;
public class Solution {
    public int minNumberInRotateArray(int [] array) {
        if(array.length == 0){
            return 0;//因傳入?yún)?shù)而導(dǎo)致題目無意義
        }
        /*初值設(shè)定
        * left : 數(shù)組起始索引 0
        * right: 數(shù)組尾部索引 n - 1
        * mid  : 中間值索引
        */
        int left = 0;
        int right = array.length - 1;
        int mid = (left + right ) / 2;
        
        //只有l(wèi)eft值 > right值，二分才有意義
        //等于時(shí)，需要暴力查找
        while(array[left] > array[right]){
            //假設(shè)left和right已經(jīng)只相差1了，說明已經(jīng)找到了。
            //此時(shí)left指向最大值，right指向最小值
            //由于while條件不取等，所以不會出現(xiàn)left = right情況
            if(left == right - 1){
                mid = right;
                break;
            }
            //找到中間索引值
            mid = (left + right) / 2;
            //mid在第一段非減區(qū)間
            if(array[left] <= array[mid]){
                left = mid;
            }
            //mid在第二段非減區(qū)間
            else{
                right = mid;
            }
        }
        //左右側(cè)相等時(shí)，暴力搜索
        if(array[left] == array[right]){
            for(int i = left; i < right; i++){
                //mid鎖定最小array值位置
                mid = (array[mid] < array[i])? mid : i;
            }
        }
        return array[mid];
    }
}