LeetCode-热题100：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：

输入： 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 次旋转

代码及注释

func findMin(nums []int) int {
    left, right := 0, len(nums) - 1 

    // 循环直到左指针超过右指针
    for left <= right {
        // 如果右指针对应的值大于或等于左指针对应的值，说明数组是升序的，直接返回左指针对应的值
        if nums[right] >= nums[left] {
            return nums[left]
        }

        // 如果只剩下两个元素，返回右指针对应的值，因为数组升序已经判断过了，因此这里直接可以知道nums[right] < nums[left]
        if right - left == 1 {
            return nums[right]
        }

        mid := (left + right) / 2
        
        // 如果中间值是最小值，返回中间值
        if nums[mid] <= nums[mid - 1] && nums[mid] <= nums[mid + 1] {
            return nums[mid]
        }

        // 如果中间值大于等于左指针对应的值，说明最小值在右半部分，更新左指针
        if nums[mid] >= nums[left] {
            left = mid + 1
        } else { // 否则，最小值在左半部分，更新右指针
            right = mid - 1
        }
    }
    return 0
}

代码解释

1. 初始化左右指针:

   • left 指向数组的第一个元素。
   • right 指向数组的最后一个元素。

2. 循环查找最小值:

   • 如果 nums[right] >= nums[left]，说明数组是升序的，直接返回 nums[left]。
   • 如果只剩下两个元素 (right - left == 1)，因为数组升序已经判断过了，因此这里直接可以知道nums[right] < nums[left]，返回 nums[right]。
   • 计算中间值 mid。
   • 如果 nums[mid] <= nums[mid - 1] && nums[mid] <= nums[mid + 1]，说明 mid 是最小值，返回 nums[mid]。
   • 如果 nums[mid] >= nums[left]，说明最小值在 mid 右侧，更新 left = mid + 1。
   • 否则，最小值在 mid 左侧，更新 right = mid - 1。

这段代码的时间复杂度是 O(log n)，其中 n 是数组 nums 的长度。