How do I handle duplicates in this problem?

To handle duplicates, you may need to adjust the boundaries of your binary search, reducing the search space incrementally when duplicates are encountered. If duplicates are on both sides of the middle element, shift your search boundaries inward to avoid redundant checks.

Can the time complexity ever reach O(n)?

Yes, in the worst case, when the array is filled with many duplicates, the time complexity can degrade to O(n) as you may need to check every element.

What is the optimal solution for this problem?

The optimal solution uses binary search with careful handling of duplicates. This allows the time complexity to be reduced to O(log n) in many cases, but may still require O(n) in the worst case due to duplicates.

How do I know when to reduce the search space in binary search?

You should reduce the search space when the middle element is greater than the rightmost element. However, when duplicates are present, you may need to carefully compare left, middle, and right elements to ensure you're correctly narrowing down the minimum element.

Is this problem solvable without binary search?

While it's possible to solve this problem without binary search by using linear scans, binary search is preferred due to its efficiency. A linear scan would result in O(n) time complexity, which is suboptimal compared to the potential O(log n) with binary search.

#154

Hard

auto_awesome二分·搜索·答案·空间

LeetCode 题解工作台

寻找旋转排序数组中的最小值 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] 注意，数…

数组二分查找

题目描述

已知一个长度为 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 次旋转

进阶：这道题与寻找旋转排序数组中的最小值类似，但 nums 可能包含重复元素。允许重复会影响算法的时间复杂度吗？会如何影响，为什么？

lightbulb

解题思路

方法一：二分查找

若 nums[mid] > nums[right]，说明最小值在 mid 的右边；若 nums[mid] < nums[right]，说明最小值在 mid 的左边（包括 mid）；若相等，无法判断，直接将 right 减 1。循环比较。

最后返回 nums[left] 即可。

时间复杂度 O(logn)。

1

2

3

4

5

6

7

8

9

10

11

12

13

class Solution:
    def findMin(self, nums: List[int]) -> int:
        left, right = 0, len(nums) - 1
        while left < right:
            mid = (left + right) >> 1
            if nums[mid] > nums[right]:
                left = mid + 1
            elif nums[mid] < nums[right]:
                right = mid
            else:
                right -= 1
        return nums[left]

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Tests how the candidate handles the trade-off between efficiency and correctness when dealing with duplicates in binary search.
question_mark
Assesses the ability to modify standard algorithms (binary search) to handle edge cases, such as duplicate values and rotations.
question_mark
Evaluates the candidate's ability to reason about the problem and identify when and why to adjust search boundaries in a rotated array.

warning

常见陷阱

外企场景

error
Misunderstanding the handling of duplicates, leading to inefficient solutions that don't maintain the correct time complexity.
error
Failing to recognize when the search space should be reduced due to duplicate values, causing the algorithm to behave like a linear search in the worst case.
error
Not properly handling edge cases where the array is very small or where the array contains multiple equal elements near the pivot point.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Rotate the array more times (larger rotations), requiring better insight into how the array structure behaves after multiple rotations.
arrow_right_alt
Use this pattern to find the maximum value instead of the minimum by reversing the logic of the binary search.
arrow_right_alt
Implement an iterative approach rather than a recursive binary search, which might better handle larger inputs with fewer function calls.

help

常见问题

外企场景

继续练习

#153 寻找旋转排序数组中的最小值 #162 寻找峰值 #167 两数之和 II - 输入有序数组