LeetCode-153-寻找旋转排序数组中的最小值

一：题目描述：

已知一个长度为 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:

1
2
3

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

示例 2:

1
2
3

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

示例 3:

1
2
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(logn)来说，就要想到二分法了
- 本道题主要是对原有的有序数组进行了旋转
- 那么就要分区间来判断，再进行二分，划定区域
- 如果middle元素大于right边界元素，那么就说明，最小值在middle右边
- 如果middle元素小于right边界元素，那么说明最小元素在middle左边或者就是middle元素
- 如果中间元素和右边元素相同，无法确定最小值在哪一边，那么让right边界向左缩小继续查找
最终left，middle，right都会在一个下标，即最小元素

四：代码 + 复杂度分析

/**
 * @param {number[]} nums
 * @return {number}
 */
var findMin = function(nums) {
    //升序 Ologn 二分
    //根据与中间元素右右边边界元素进行判断划分区间
    let left = 0
    let right = nums.length - 1
    //1。 如果最左边元素小于最右边元素 说明未旋转
    if(nums[left] < nums[right]) return nums[left]

    //2. 旋转
    //划分区间 左闭右闭
    while(left <= right) {
        //更新middle
        //避免整数之和大于整数范围溢出 导致结果NaN
        let middle = Math.floor((right - left) / 2) + left
        //判断中间middle元素与最右边元素的关系
        //如果middle元素大于右边元素 说明最小值再右侧
        if(nums[middle] > nums[right]) {
            left = middle + 1
        }else if(nums[middle] < nums[right]) {
        // 如果中间元素小于右边界元素，说明最小值在左半边或就是中间元素本身
            right = middle
        }else {
            //中间元素和右边元素相等 右边界左移
            right--
        }
    }
    //直到三个指针同指向一个元素
    return nums[left]
};

时间复杂度：
- O(logn)：二分法搜索最小元素
空间复杂度：O（1）
- 只创建了left，right，middle变量