九章演算法 | 微軟面試題：尋找旋轉排序陣列中的最小值
假設一個排好序的陣列在其某一未知點發生了旋轉（比如0 1 2 4 5 6 7 可能變成4 5 6 7 0 1 2）。你需要找到其中最小的元素。
線上評測地址：LintCode 領釦
樣例 1：
輸入：［4， 5， 6， 7， 0， 1， 2］
輸出：0
解釋：
陣列中的最小值為0
樣例 2：
輸入：［2，1］
輸出：1
解釋：
陣列中的最小值為1
解題思路
最直接的是暴力解法，搜尋整個陣列找到最小元素，時間複雜度為O（n）。
我們可以旋轉陣列的特性，用改進後的二分查詢來解決，時間複雜度為O（logn）。
演算法流程
使用二分法來尋找最小值，如圖所示可以幫助我們理解演算法過程。
設定雙指標left和right指向陣列nums兩端。
第一次分類討論：比較nums［left］和nums［right］
如果nums［left］ < nums［right］，說明陣列沒有旋轉過，仍然是升序排列。我們直接return nums［left］。
反之，說明陣列非單調，進入到第二次分類討論。
第二次分類討論：比較nums［left］和nums［mid］，其中mid是二分中點。
如果nums［left］ > nums［mid］，可以證明此時陣列右半邊是升序的，那我們就不用考慮右半邊了。最小值一定在［left， mid］間，令right = mid。
如果nums［left］ <= nums［mid］，可以證明此時陣列左半邊是升序的，於是我們不需要考慮左半邊。最小值一定在（mid， right］間，令left = mid + 1。
直到left == right時，此時指向的就是最小值，return nums［left］。
等效方法
上述演算法中，第二次分類討論我們比較的是nums［left］和nums［mid］的大小關係，其實比較nums［right］和nums［mid］的大小也是一樣的。
nums［left］ > nums［mid］，等效於nums［mid］ < nums［right］
nums［left］ <= nums［mid］，等效於nums［mid］ > nums［right］
有興趣可以證明一下。程式碼如何實現，看個人的preference啦。
複雜度分析
時間複雜度： O（log（n）），n為nums的長度。同二分查詢的時間複雜度。
空間複雜度： $O（1） $。沒有使用額外空間。
public
class
Solution
{
/**
* @param nums： a rotated sorted array
* @return： the minimum number in the array
*/
public
int
findMin
（
int
［］
nums
）
{
int
left
=
0
，
right
=
nums
。
length
-
1
；
// 二分法
while
（
left
<
right
）{
// 最小值在left
if
（
nums
［
left
］
<
nums
［
right
］）{
return
nums
［
left
］；
}
int
mid
=
left
+
（
right
-
left
）
/
2
；
// 最小值在［left， mid］
if
（
nums
［
left
］
>
nums
［
mid
］）{
right
=
mid
；
}
// 最小值在（mid， right］
else
{
left
=
mid
+
1
；
}
}
return
nums
［
left
］；
}
}
更多題解參考：九章演算法