题目描述

假设按照升序排序的数组在预先未知的某个点上进行了旋转。

( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。

请找出其中最小的元素。

你可以假设数组中不存在重复元素。

示例一：

1 2	输入: [3,4,5,1,2] 输出: 1

示例二：

1 2	输入: [4,5,6,7,0,1,2] 输出: 0

题解

二分查找

因为不存在重复的数字, 所以只需要考虑大于和等于的情况, 比较对象为nums[right]

循环二分：设置 i,j 指针分别指向numbers 数组左右两端，m = (i + j) / 2 为每次二分的中点（ “/“ 代表向下取整除法），可分为以下三种情况：
1. 当numbers[m] > numbers[j]时： m 一定在左排序数组中，即旋转点 x一定在[m + 1, j]闭区间内，因此执行i = m + 1；
2. 当 numbers[m] < numbers[j]时： m 一定在右排序数组中，即旋转点 x 一定在[i, m] 闭区间内，因此执行j = m；
返回值：当i = j时跳出二分循环，并返回 numbers[i]即可。

class Solution {
    public int findMin(int[] nums) {
        int left = 0;
        int right = nums.length - 1;

        while (left < right) {
            int mid = (left + right) / 2;
            if (nums[mid] < nums[right]) {
                right = mid;
            } else if (nums[mid] > nums[right]) {
                left = mid + 1;
            }
        }
        return nums[left];
    }
}