题目

假设按照升序排序的数组在预先未知的某个点上进行了旋转。

(例如，数组 [0, 1, 2, 4, 5, 6, 7] 可能变为 [4, 5, 6, 7, 0, 1, 2])。

请找出其中最小的元素。

注意数组中可能存在重复的元素。

示例 1：

输入: [1,3,5]
输出: 1

示例 2：

输入: [2,2,2,0,1]
输出: 0

说明：

• 允许重复会影响算法的时间复杂度吗？会如何影响，为什么？

方案一

func findMin(nums []int) int {
    // 特殊情况
    if len(nums) == 0 {return -1}

    var left, right = 0, len(nums) - 1
    // 如果是从重复的值中间进行旋转的，二分查找会很麻烦，
    // 所以这里整理为如果是从重复的值中间旋转的，就去除前面的部分
    // 但是最坏的情况下时间复杂度将会退化到 O(n)
    // eg1. [10, 10, 1, 10, 10, 10, 10] -> [1, 10, 10, 10, 10]
    // eg2. [3, 3, 3, 1] -> [3, 3, 3, 1]
    for left < right {
        if nums[left] != nums[right] {
            break
        }
        left += 1
    }
    if nums[left] <= nums[right] {return nums[left]} // 升序的情况

    for left + 1 < right {
        var mid = (left + right) / 2

        if nums[mid] > nums[mid + 1] { // 必须先判断这个，因为当 len(nums) == 2 时 mid = 0
            return nums[mid + 1]
        } else if nums[mid] < nums[mid - 1] {
            return nums[mid]
        } else if nums[mid] >= nums[left] { // 这里的等号参考 eg2
            left = mid
        } else {
            right = mid
        }
    }

    if nums[left] < nums[right] {
        return nums[left]
    } else {
        return nums[right]
    }
}

方案二（leetcode）

func findMin(nums []int) int {
    var left, right = 0, len(nums)-1
    for left < right {
        var mid = (left + right) >> 1
        if nums[mid] < nums[right] {
            right = mid
        } else if nums[mid] > nums[right] {
            left = mid + 1
        } else {
            right--
        }
    }
    return nums[left]
}

• 在二分查找的基础上修改而成，非常有创意
• 摒弃了在二分查找中间直接寻找到目标节点并返回的过程
  • 可能会导致时间复杂度增高，但是如果加上则需要判断很多特殊情况，导致代码复杂度增加
  • 比如数组旋转后依然是升序，或者数组长度 == 1
• 注意最后一个 else 的 right--
• 最坏情况下的时间复杂度为 O(n)，数组内值全相等时发生。

方案三（查阅代码leetcode后实现）

func findMin(nums []int) int {
    var left, right = 0, len(nums) - 1
    for left + 1 < right {
        var mid = (left + right) / 2
        if nums[mid] > nums[mid + 1] {
            return nums[mid + 1]
        } else if nums[mid] < nums[mid - 1] {
            return nums[mid]
        } else if nums[mid] < nums[right] {
            right = mid
        } else if nums[mid] > nums[right] {
            left = mid
        } else {
            right--
        }
    }

    if nums[left] <= nums[right] {
        return nums[left]
    } else {
        return nums[right]
    }
}

• 在方案二的基础上增加了二分查找过程中找到目标节点则直接返回的过程；
• 最坏情况下的时间复杂度为 O(n)，数组内值全相等时发生；

原文

https://leetcode-cn.com/explore/learn/card/binary-search/214/more-practices/854/