# 0154. 寻找旋转排序数组中的最小值 II

## 题目地址(154. 寻找旋转排序数组中的最小值 II)

<https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array-ii/>

## 题目描述

```
已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。例如，原数组 nums = [0,1,4,4,5,6,7] 在变化后可能得到：
若旋转 4 次，则可以得到 [4,5,6,7,0,1,4]
若旋转 7 次，则可以得到 [0,1,4,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 ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。



示例 1：

输入：nums = [1,3,5]
输出：1


示例 2：

输入：nums = [2,2,2,0,1]
输出：0




提示：

n == nums.length
1 <= n <= 5000
-5000 <= nums[i] <= 5000
nums 原来是一个升序排序的数组，并进行了 1 至 n 次旋转



进阶：

这道题是 寻找旋转排序数组中的最小值 的延伸题目。
允许重复会影响算法的时间复杂度吗？会如何影响，为什么？
```

## 前置知识

* [二分](https://github.com/azl397985856/leetcode/blob/master/thinkings/binary-search-1.md)

## 公司

* 暂无

## 思路

和 153 题目类似，只不过这道题在 153 的基础上增加了“可能重复”的条件。

沿用 153 的思路：

* 如果左端点的值小于右端点的值则可以提前退出。
* 否则我们选取中点，并判断中点的位置是在左边有序部分还是右边有序部分。
* 如果在左边有序部分，那么 r = mid，如果在右边有序部分则 l = mid + 1

问题的关键是**有时候我们是没有办法判断 mid 是在左边有序部分还是右边有序部分的。** 比如 nums\[mid] == nums\[l]，就可能对应下面的两种情况：

1. \[2,2,2,2,0,1,2] 此时 mid 在左侧有序部分
2. \[2,0,1,2,2,2] 此时 mid 在右侧有序部分

这个时候我们无法排除一半。退而求其次，我们只能排除一个，这个是算法的关键，这同时意味着我们的算法无法在最坏的情况下达到 $logn$，这和我们平时用的比较多的二分是不一样的。

那么在这种无法判断是在左边有序部分还是右边有序部分的情况下，我们应该舍弃左端点还是右端点呢？

答案是选择舍弃右端点，因为舍弃右端点不会错过最小值。之所以选择舍弃右端点不会错过最小值有一个前提：**取中点逻辑是向下取整**，如果你取中点是向上取整情况就有所不同了。

另外需要注意的是，我们选择判断是在左侧有序部分还是右边有序部分，**需要用 mid 和右端点进行比较，而不能是左端点。**&#x8FD9;是因为使用左端点无法在任何情况舍弃一半，读者不妨自己试试看。

## 关键点

* 比较右端点而不是左端点
* 如果左端点的值小于右端点的值则可以提前退出

## 代码

* 语言支持：Python3

Python3 Code:

```python
class Solution:
    def findMin(self, nums: List[int]) -> int:
        l, r = 0, len(nums) - 1

        while l < r:
            if nums[l] < nums[r]:
                return nums[l]
            mid = (l + r) // 2
            # [2,2,2,0,1]
            if nums[mid] > nums[r]:
                l = mid + 1
            elif nums[mid] < nums[r]:
                r = mid
            else:
                r -= 1

        return nums[l]  # or nums[r]
```

**复杂度分析**

令 n 为数组长度。

* 时间复杂度：$O(n)$，最坏的情况我们需要扫描整个数组。
* 空间复杂度：$O(1)$


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/hard/154.find-minimum-in-rotated-sorted-array-ii.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.