153. Find Minimum in Rotated Sorted Array

https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/

solution from https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array/solution/er-fen-fa-fen-zhi-fa-python-dai-ma-java-dai-ma-by-/

二分法也可以解決這個問題，因為“旋轉排序數組”，幾乎有序的數組，也可以通過比較特定位置的元素的值的判斷達到“減治”的效果（逐漸縮小搜索區間）。

很自然地，我們會看中間數（位於待搜索區間中間位置的元素，由於不是有序數組，因此不能稱之為中位數）。

另外，待搜索區間頭和尾的元素是位置特殊的元素。有兩個比較自然的思路是：

思路1：看看當前搜索區間的左邊界和“中間數”（注意這裡不是中位數），是不是可以縮小搜索區間的範圍；

思路2：看看當前搜索區間的右邊界和“中間數”（注意這裡不是中位數），是不是可以縮小搜索區間的範圍；

要想清楚這個問題，我們不妨舉幾個例子。

針對思路1： 例1：[1, 2, 3, 4, 5]

例2：[2, 3, 4, 5, 1]

這兩個例子的“中間數”都比左邊界大，但是“旋轉排序數組”的最小值一個在“中間數”的左邊，一個在“中間數”的右邊，因此思路1 不可行。

針對思路2，依然寫兩個例子，這兩個例子分別是“中間數比右邊界大”和“中間數比右邊界小”，看看能不能推導出一般化的結論。 例3：[7, 8, 9, 10, 11, 12, 1, 2, 3]

“中間數” 11比右邊界3大，因此中間數左邊的數（包括中間數）都不是“旋轉排序數組”的最小值，因此，下一輪搜索的區間是[mid + 1, right]，將下一輪搜索的左邊界設置成中間數位置+ 1，即left = mid + 1。

例4：[7, 8, 1, 2, 3]

“中間數” 1比右邊界3小，說明，中間數到右邊界是遞增的，那麼中間數右邊的（不包括中間數）一定不是“旋轉排序數組”的最小值，可以把它們排除，但中間數有可能是整個數組中的最小值，就如本例，因此，在下一輪搜索區間是[left, mid]，於是把右邊界設置為right = mid。

從例3 和例4 可以看出，不論中間數比右邊界大，還是中間數比右邊界小，我們都可以排除掉將近一半的元素，把原始問題轉換成一個規模更小的子問題，這正是“減而治之”思想的體現，因此思路2 可行。

/*
    time complexity: O(logn), space complexity: O(1)
*/
class Solution {
    public int findMin(int[] nums) {
        int left = 0;
        int right = nums.length - 1;
        
        while (left < right) {
            int mid = (left + right) >>> 1;
            if (nums[mid] > nums[right]) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return nums[left];
    }
}