What is the main algorithmic approach for solving the 'Find Minimum in Rotated Sorted Array' problem?

The main approach is binary search, which allows you to identify the pivot point in the rotated array and find the minimum element in O(log n) time.

How does binary search work in the context of finding the minimum in a rotated array?

In binary search, the array is split into two halves. By comparing the middle element with the rightmost element, we can determine which half contains the minimum, narrowing the search range until we find it.

What is the time complexity of the solution for this problem?

The time complexity is O(log n) because binary search reduces the problem size by half with each iteration, making it much more efficient than a brute-force O(n) solution.

Are there any edge cases I need to consider when solving this problem?

Yes, edge cases include when the array is not rotated at all, where the first element will be the minimum. Also, consider arrays with only one element, where the minimum is trivially the single element.

Can I solve this problem using a brute-force approach?

While a brute-force solution with O(n) time complexity will work, it is less efficient compared to the optimal O(log n) solution using binary search.

#153

Medium

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

LeetCode 题解工作台

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

已知一个长度为 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] 注意，数…

数组二分查找

题目描述

已知一个长度为 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] ，旋转 4 次得到输入数组。

示例 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 次旋转

lightbulb

解题思路

方法一：二分查找

初始，判断数组首尾元素的大小关系，若 nums[0] <= nums[n - 1] 条件成立，则说明当前数组已经是递增数组，最小值一定是数组第一个元素，提前返回 nums[0]。

否则，进行二分判断。若 nums[0] <= nums[mid]，说明 [left, mid] 范围内的元素构成递增数组，最小值一定在 mid 的右侧，否则说明 [mid + 1, right] 范围内的元素构成递增数组，最小值一定在 mid 的左侧。

除了 nums[0]，也可以以 nums[right] 作为参照物，若 nums[mid] < nums[right] 成立，则最小值存在于 [left, mid] 范围当中，否则存在于 [mid + 1, right]。

时间复杂度： $O(logN)$

1

2

3

4

5

6

7

8

9

10

11

12

13

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

speed

复杂度分析

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

psychology

面试官常问的追问

外企场景

question_mark
Candidate demonstrates understanding of binary search for searching in rotated arrays.
question_mark
Candidate is able to identify the pivot point and explain how binary search narrows down the minimum element.
question_mark
Candidate should address edge cases and explain the solution's efficiency.

warning

常见陷阱

外企场景

error
Incorrectly identifying the pivot, leading to an inefficient or incorrect solution.
error
Not handling the case where the array is not rotated, resulting in unnecessary computations.
error
Using a brute force approach (O(n)) instead of binary search, missing the performance benefits.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Find the maximum element in a rotated sorted array.
arrow_right_alt
Find the minimum element in a rotated sorted array with duplicate elements.
arrow_right_alt
Find the rotation point in the array without explicitly finding the minimum element.

help

常见问题

外企场景

继续练习

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