劍指offer_11_旋轉數組中的最小數字

描述：把一個數組最開始的若幹個元素搬到數組的末尾，我們稱之為數組的旋轉。輸入一個遞增排序的數組的一個旋轉，輸出旋轉數組的最小元素，排序的旋轉數組定義如下：

如：{1,2,3,4,5}的一個旋轉數組為{3,4,5,1,2} 該數組的最小值為1           

複制

初看題目我們最直覺的解法并不難，周遊數組用倆個"指針"一前以後，目前面"指針"指向的元素比後面的"指針"指向的數組元素小時，這時我們就找到旋轉數組中的最小元素，我們不難寫出如下代碼：

public static int findMin(int[] arr) {
    // 如果數組是隻有一個元素 則不是旋轉數組同時也防止下邊的i+1越界
    if(arr == null || arr.length <= 1){
        return -1;
    }

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

複制

但是上面這種方法當數組的元素特别多時，效率是比較低的，不足以拿到offer，現在考慮用二分法對上面算法進行改良：

定義一個數組最左邊的"指針"left和一個數組最右邊的"指針"right，每次求倆個指針的中間值記為middle，如果left所對應的值要比middle小，那麼說明數組還在遞增中，最小值會在middle和right之間，這時候我們讓left等于middle，繼續用同樣的方式縮小範圍，如果middle要比right小，那麼說明最小值在left和middle之間，讓right等于middle，用同樣的方式繼續求下去，就能求到最小值啦。

public static int findMin(int []arr) {
    int left = 0;
    int right = arr.length;
    while(left < right) {
        int middle = (left + right) / 2;
        if (arr[left] < arr[middle]) {
            left = middle;
        // 如果遇到相同的元素 我們就隻能用周遊了
        } else if(arr[left] == arr[middle]){
            for(int i = left; i <= middle; i++) {
                if(arr[i] < arr[middle]) {
                    return arr[i];
                }
            }
            return arr[left];
        } else{
            right = middle;
        }
        if (right - left == 1) {
            if(arr[right] > arr[left])
                return arr[left];
            else
                return arr[right];
        }
    }
    return  arr[left];
}           

複制

當left對應的元素與right對應的元素相等時，這是特殊情況，這裡選擇周遊去找最小值。