【算法】寻找旋转排序数组中的最小值难度：中等； 已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转

难度：中等；

已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。例如，原数组 nums = [0,1,2,4,5,6,7] 在变化后可能得到：

• 若旋转 4 次，则可以得到 [4,5,6,7,0,1,2]
• 若旋转 7 次，则可以得到 [0,1,2,4,5,6,7]

注意，数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。

给你一个元素值 互不相同 的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。

你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。

示例 1：

输入：nums = [3,4,5,1,2]
输出：1
解释：原数组为 [1,2,3,4,5] ，旋转 3 次得到输入数组。

示例 2：

输入：nums = [4,5,6,7,0,1,2]
输出：0
解释：原数组为 [0,1,2,4,5,6,7] ，旋转 3 次得到输入数组。

示例 3：

输入：nums = [11,13,15,17]
输出：11
解释：原数组为 [11,13,15,17] ，旋转 4 次得到输入数组。

提示：

• n == nums.length

• 1 <= n <= 5000

• -5000 <= nums[i] <= 5000

• nums 中的所有整数 互不相同

• nums 原来是一个升序排序的数组，并进行了 1 至 n 次旋转

解题思路：

旋转排序数组是指原本升序排序的数组在某些位置进行了旋转，导致数组的排序变得复杂，但依然保留了两段升序子数组的特性

利用旋转数组的特性，通过比较中间元素和数组最后一个元素，可以快速判断最小元素的大致位置，从而将查找范围缩小一半，实现 O(log n) 的时间复杂度。

在循环的终止条件中，当 left 和 right 相等时，意味着找到了最小元素，因为旋转数组的特性保证了最小元素是唯一的。

1. 初始化指针：设置 left 和 right 指针，分别指向数组的起始位置和结束位置。
2. 二分查找：在 left 和 right 之间进行二分查找，直到 left 和 right 指向同一个元素。
3. 比较中间元素：计算中间位置 mid，并比较 nums[mid] 和 nums[right] 的大小。

• 如果 nums[mid] >= nums[right]，说明从 mid 到 right 的子数组是升序的，但 mid 可能位于旋转点的左侧，最小元素肯定不在 [mid, right] 区间内，所以更新 left = mid + 1，继续在 [left, right) 的左半边查找。
• 如果 nums[mid] < nums[right]，说明最小元素位于 [left, mid] 区间内，包括 mid 本身，因为这表明旋转点在 mid 的右边，所以更新 right = mid，在 [left, mid] 区间内查找。

1. 终止条件：当 left == right 时，退出循环。此时，left 或者 right 指向的元素之一就是最小元素。

2. 返回结果：返回 nums[left] 或者 nums[right]（两者相同）。

JavaScript代码实现：

/**
 * @param {number[]} nums
 * @return {number}
 */
var findMin = function(nums) {
    let left = 0;
    let right = nums.length - 1;

    while (left < right) {
        let mid = Math.floor((left + right) / 2);
        if (nums[mid] >= nums[right]) {
            // 最小元素在 mid 的右边
            left = mid + 1;
        } else {
            // 最小元素在 mid 或者 mid 的左边
            right = mid;
        }
    }

    // left 和 right 相同，指向最小元素
    return nums[left];
};

// 示例调用
// console.log(findMin([3, 4, 5, 1, 2])); // 输出: 1
// console.log(findMin([4, 5, 6, 7, 0, 1, 2])); // 输出: 0