【重点】【二分查找】153.寻找旋转排序数组中的最小值

题目
更好的解法总结在：旋转数组的最小数字

法1：二分查找

最佳方法，比较mid和right！

Python

class Solution:
    def findMin(self, nums: List[int]) -> int:
        l = 0
        r = len(nums) - 1
        while l < r:
            mid = (l + r) // 2
            if nums[mid] > nums[r]: # 最小值在右边
                l = mid + 1
            else:
                r = mid             # 最小值在左边，mid可能是最小值索引

        return nums[l]

Java

class Solution {
    public int findMin(int[] nums) {
        int left = 0;
        int right = nums.length - 1;                /* 左闭右闭区间，如果用右开区间则不方便判断右值 */ 
        while (left < right) {                      /* 循环不变式，如果left == right，则循环结束 */
            int mid = left + (right - left) / 2;    /* 地板除，mid更靠近left */
            if (nums[mid] > nums[right]) {          /* 中值 > 右值，最小值在右半边，收缩左边界 */ 
                left = mid + 1;                     /* 因为中值 > 右值，中值肯定不是最小值，左边界可以跨过mid */ 
            } else if (nums[mid] < nums[right]) {   /* 明确中值 < 右值，最小值在左半边，收缩右边界 */ 
                right = mid;                        /* 因为中值 < 右值，中值也可能是最小值，右边界只能取到mid处 */ 
            }
        }
        return nums[left];    /* 循环结束，left == right，最小值输出nums[left]或nums[right]均可 */     
    }
}

稍差点方法，比较mid和left。

class Solution {
    public int findMin(int[] nums) {
        if (nums.length == 0) {
            return -1;
        }
        int left = 0, right = nums.length - 1, mid = 0;
        while (left < right) {
            mid = left + (right - left) / 2;
            if (nums[mid] >= nums[left] && nums[mid] > nums[right]) { // 左段
                left = mid + 1;
            } else if (nums[mid] <= nums[right] && nums[mid] < nums[left]) { // 右段
                right = mid; // 最小值可能是mid, 所以不再减1
            } else { // 单调
                right = mid - 1;
            }
        }

        return nums[left];
    }
}