LeetCode 153. 寻找旋转排序数组中的最小值

二分查找

考虑数组中的最后一个元素 x ：在最小值右侧的元素（不包括最后一个元素本身），它们的值一定都严格小于 x ；而在最小值左侧的元素，它们的值一定都严格大于 x 。
将中间元素 nums[mid] 与右边界元素 nums[r] 进行比较：

• nums[mid] < nums[r] ，说明 nums[mid] 是最小值右侧的元素，此时可以忽略查找区间的右半部分。
• nums[mid] > nums[r] ，说明 nums[mid] 是最小值左侧的元素，此时可以忽略查找区间的左半部分。

class Solution {
    public int findMin(int[] nums) {
        int l = 0, r = nums.length - 1;
        while (l < r) {
            int mid = (l + r) / 2;
            if (nums[mid] < nums[r]) r = mid;
            else l = mid + 1;
        }
        return nums[l];
    }
}

• 时间复杂度：O(logn)
• 空间复杂度：O(1)