153. Find Minimum in Rotated Sorted Array

class Solution {
    public int findMin(int[] nums) {
        int left = 0, right = nums.length - 1; // [left, right]
        while (left < right) { // 此题没有使用小于等于是因为最后一个元素无需搜索，为最小值
            int mid = (left + right) >>> 1;
            if (nums[mid] < nums[right]) { // nums[mid] 与 nums[right] 不可能相等，因为最小区间至少含有两个元素
                right = mid; // nums[right] 可能为最小值，缩小范围至 [left, mid]
            } else {
                // nums[mid] > nums[right]
                left = mid + 1; // nums[mid] 不可能为最小值，缩小范围至 [mid + 1, right]
            }
        }

        return nums[left]; // 注意题目要求返回元素值而不是索引
    }
}

关键点在于与右端元素相比较，而不是相邻元素比较，否则 nums = [2, 3, 4, 5, 1] 无法 AC。

References

153. Find Minimum in Rotated Sorted Array