劍指 Offer 11. 旋轉數組的最小數字
leetcode題目連結：https://leetcode-cn.com/problems/xuan-zhuan-shu-zu-de-zui-xiao-shu-zi-lcof
把一個數組最開始的若幹個元素搬到數組的末尾，我們稱之為數組的旋轉。輸入一個遞增排序的數組的一個旋轉，輸出旋轉數組的最小元素。例如，數組 [3,4,5,1,2] 為 [1,2,3,4,5] 的一個旋轉，該數組的最小值為1。
示例 1：
輸入：[3,4,5,1,2]
輸出：1
示例 2：
輸入：[2,2,2,0,1]
輸出：0
解題思路：
1.首先需要了解什麼是旋轉數組。 關于旋轉數組指的是
把一個有序數組的末尾一部分移動到數組的頭部
。這個有序數組在題目中是可以有重複元素的。舉個比例，比如數組[1,2,2,3,4,5]，将數組尾部的[3,4,5]移動到頭部，即[3,4,5,1,2,2]，它就是元素組的旋轉數組。
2.暴力解法
旋轉數組是有序的，可以把它看成是兩段升序的數組。比如題中的[3,4,5,1,2] 可以看作是[3,4,5]，[1,2]兩個數組。那麼從數組的頭部開始周遊，
直到index的下一個元素index+1比它小
的時候，它一定是整個數組的最小值。隻需要
傳回arr[index+1]
就可以得到解。這樣時間複雜度是線性的，具體的來說是O(index)的。
3.看成是求有序數組的最小值。 其實這道題就是求一個數組升序排序後的頭部元素。
使用系統提供的api然後傳回arr[0]也可以直接解決
，但這違背了算法的思想。
4.使用二分法
二分搜尋一般使用在一個有序的數組中，旋轉數組可以看作是兩段有序的數組。如題利用二分搜尋的思想為數組[3,4,5,1,2]設定三個指針分别指向左側，右側和中間。
每一次讓中間和最右側數做比較，如圖
arr[mid]>arr[right]
，那麼在閉區間[left,mid]中的所有元素一定全部都是大于right所在元素的。那麼需要尋找的最小值一定在閉區間[mid+1,right]裡。新的查找範圍更新
left=mid+1
，這是因為5已經大于2了，沒必要在進行判斷。
同理： 在如上圖的例子中，
arr[mid]<arr[right]
，那麼在[mid+1，right]的閉區間一定都是大于arr[mid]的，那麼下一次的查找範圍是[left,mid]。此時應該
更新right=mid
，對于二分搜尋法比較熟悉的話，可能會想到不應該是更新right = mid-1嗎？但是在
這裡的arr[mid]隻是比arr[right]小
，上圖的例子就剛好是arr[mid]的特殊情況，如果從[left,mid-1]向前搜尋的話，就無法找到最小值。
需要注意的是，上面是沒有重複元素的情況，如果存在重複元素的旋轉數組呢？
如上圖的兩種情況都是
arr[mid] ==arr[right]
，此時就無法判斷到底是向前取區間或者向後取區間。
是以當arr[mid] ==arr[right]時，
right--
那麼相應的mid的位置也會發生變化，再次比較發現arr[mid]<arr[rigth]。這時就回到了上一步，取前面的區間。最終當left=right時，就找到了目标值，此時傳回arr[left]。
最終的代碼實作
class Solution {
public int minArray(int[] numbers) {
int left = 0;
int right = numbers.length - 1;
if (right == 0)
return numbers[0];
while (left < right) {
int mid = (right - left) / 2 + left;
if (numbers[mid] == numbers[right])
right--;
else if (numbers[mid] > numbers[right])
left = mid + 1;
else if (numbers[mid] < numbers[right])
right = mid;
}
return numbers[left];
}
}
此外，解決這道問題同時可以解決leetcode154号問題，他們是一樣的：154. 尋找旋轉排序數組中的最小值 II