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

故事背景

想象你有一排按顺序排列的数字卡片，比如 [1, 2, 3, 4, 5]。有一天，你决定玩一个游戏，把这些数字卡片的一部分移到了队列的后面，比如 [3, 4, 5, 1, 2] 或者 [4, 5, 1, 2, 3]。现在你要从这些卡片中找到最小的那个数字。

解题思路

1. 确定起点和终点：
1. 我们需要知道从哪里开始找，哪里结束找。
2. 我们可以把数组的第一个数字作为起点，最后一个数字作为终点。
2. 中间点：
1. 接下来，我们需要找到数组的中间点，看看中间点的数字是多少。
3. 判断中间点：
1. 如果中间点的数字比终点的数字小，那么最小的数字肯定在左边。
2. 如果中间点的数字比终点的数字大，那么最小的数字肯定在右边。
4. 重复步骤：
1. 我们不断地重复上面的步骤，每次都将搜索的范围缩小一半，直到找到最小的数字为止。

代码解释

让我们用简单的语言来解释代码：

import java.util.Arrays;

public class Solution {

    /**
     * 查找旋转数组中的最小值
     * @param nums 旋转数组
     * @return 最小值
     */
    public int findMin(int[] nums) {
        if (nums == null || nums.length == 0) {
            throw new IllegalArgumentException("Array is empty or null");
        }

        int left = 0; // 起点
        int right = nums.length - 1; // 终点

        // 如果数组已经是非降序的，直接返回第一个元素
        if (nums[left] < nums[right]) {
            return nums[left];
        }

        while (left < right) {
            int mid = left + (right - left) / 2; // 找到中间点

            // 如果中间点的数字小于终点的数字，那么最小的数字在左边
            if (nums[mid] < nums[right]) {
                right = mid;
            } else if (nums[mid] > nums[right]) {
                // 如果中间点的数字大于终点的数字，那么最小的数字在右边
                left = mid + 1;
            } else {
                // 如果相等，则向左移动一位（这种情况很少见，可以省略）
                right--;
            }
        }

        return nums[left]; // 返回找到的最小值
    }


}

解释

1. 初始化指针：
1. left 指向数组的起始位置。
2. right 指向数组的结束位置。
2. 二分查找：
1. 如果 nums[left] < nums[right]，则整个数组已经是非降序的，最小值就是 nums[left]。
2. 如果 nums[mid] < nums[right]，那么最小值位于左半边，更新 right = mid。
3. 如果 nums[mid] > nums[right]，那么最小值位于右半边，更新 left = mid + 1。
3. 退出条件：
1. 当 left == right 时，找到了最小值。

测试结果

• 输入：[3, 4, 5, 1, 2]
• 输出：1
• 输入：[3, 100, 200, 3]
• 输出：3
• 输入：[1, 2, 3, 4, 5]
• 输出：1

用人话来解释代码

1. 初始化指针：
1. left 表示从哪里开始找。
2. right 表示在哪里结束找。
2. 检查是否已经是非降序：
1. 如果起点的数字比终点的小，说明已经是非降序了，那么最小的数字就是起点的数字。
3. 不断寻找中间点：
1. 每次找到中间点，看看中间点的数字和终点的数字哪个小。
2. 如果中间点的数字比终点的小，那么最小的数字肯定在左边。
3. 如果中间点的数字比终点的大，那么最小的数字肯定在右边。
4. 不断缩小范围：
1. 每次根据中间点的数字调整起点或终点的位置，直到找到最小的数字。

如果这篇文章对你有帮助，请点个免费的赞👍，让它能够帮助更多的人。