题解 | #旋转数组的最小数字#

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param nums int整型一维数组
     * @return int整型
     */
    public int minNumberInRotateArray (int[] nums) {
        // write code here
        // 整个问题本是上是在找数组中唯一存在的极小值，采取二分法解决

        // 算法的时间复杂度O(logN)，额外空间复杂度O(1)

        int n = nums.length;
        if (n == 1) {
            // 如果只有一个元素
            return nums[0];
        }
        if (n == 2) {
            // 如果只有两个元素
            return Math.min(nums[0], nums[1]);
        }
        // 确保有三个以上的元素
        int l = 0;
        int r = n - 1;

        // 采用二分思想，任务是找到这样一个转折点[↗……↗（↘index）↗……↗]，其特征是左边比它大，右边也比它大
        int min = nums[l];
        while (l < r) {
            // 因为数组非递减，且涉及到右划l
            // 所以采用一个变量min时刻与当前最左的l元素比较总不是坏事
            min = Math.min(min, nums[l]);
            int mid = (l + r) / 2;
            if (nums[l] > nums[mid]) {
                // 如果mid处比最左处要小，即[↗……↗（↘index）↗……mid……↗]，说明局部最小值一定在左半区（或mid本身）
                r = mid;
            } else if (nums[l] < nums[mid]) {
                // 如果mid处比最左处要大，即[↗……mid……↗（↘index）↗……↗]，说明局部最小值一定在右半区（必不包括mid）
                l = mid + 1;
            } else {
                // 如果mid处与最左处相等，即[-->……mid……-->（↘index）↗……-->]，或[-->……-->（↘index）↗……-->……mid……-->]，在左还是在右不能确定
                // 但是！至少说明l处一定不是极小值点，此时l往右移一位，缩小范围即可
                l++;
            }
        }

        return Math.min(min, nums[l]);
    }
}