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

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param nums int整型一维数组
     * @return int整型
     */
    public int minNumberInRotateArray (int[] nums) {
        // 排序数组的查找问题可以优先考虑二分法解决。
        if (nums.length == 0) {
            return 0;
        }

        int left = 0;
        int right = nums.length - 1;

        while (left < right) {
            int mid = left + (right - left) / 2;

            // 如果 nums[mid] < nums[right]，说明最小值在 mid 左侧或 mid 本身
            if (nums[mid] < nums[right]) {
                right = mid;
            }
            // 如果 nums[mid] > nums[right]，说明最小值在 mid 右侧
            else if (nums[mid] > nums[right]) {
                left = mid + 1;
            }
            // 如果 nums[mid] == nums[right]，无法确定最小值的位置，缩小范围
            else {
                right--;
            }
        }

        return nums[left];
    }
}

1. 旋转排序数组的特性：数组被分为两个有序的子数组，最小值位于两个子数组的交界处。

2. 二分查找的边界条件：设置指针left、right分别指向数组首尾。并计算中间元素的索引mid。

其中在旋转排序数组中nums[right]是右子数组的最大值，且nums[left]>= nums[right]。因此通过比较nums[mid]和nums[right]可以更加直观判断，nums[mid]是处于左子数组还是右子数组。

如果nums[mid]<nums[right] --> nums[mid]位于右子数组中，最小值在mid左侧或者mid本身。

如果nums[mid]>nums[right] --> nums[mid]位于左子数组中，最小值一定位于mid右侧。

如果nums[mid] == nums[right] --> 无法确定最小值的位置，则需要更新right下标，right--，重新进行判断。