Why is a simple binary search not enough for Search in Rotated Sorted Array II?

Because duplicates can make it impossible to determine the sorted half, requiring boundary adjustments to maintain correctness.

What is the worst-case time complexity for this problem?

O(n), which occurs when duplicates force the search to reduce boundaries one step at a time.

Can this algorithm work if there are no duplicates?

Yes, it simplifies to standard rotated binary search, achieving O(log n) consistently.

How do I know which half of the array is sorted?

Compare nums[left], nums[mid], and nums[right]; after resolving duplicates, the sorted half can be identified to decide where to continue searching.

Does GhostInterview provide code solutions for Search in Rotated Sorted Array II?

It guides through the stepwise reasoning and edge-case handling rather than giving direct code, ensuring understanding of binary search adjustments.

#81

Medium

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

LeetCode 题解工作台

搜索旋转排序数组 II

已知存在一个按非降序排列的整数数组 nums ，数组中的值不必互不相同。在传递给函数之前， nums 在预先未知的某个下标 k （ 0 ）上进行了旋转，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[…

数组二分查找

题目描述

已知存在一个按非降序排列的整数数组 nums ，数组中的值不必互不相同。

在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了旋转，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,4,4,5,6,6,7] 在下标 5 处经旋转后可能变为 [4,5,6,6,7,0,1,2,4,4] 。

给你 旋转后 的数组 nums 和一个整数 target ，请你编写一个函数来判断给定的目标值是否存在于数组中。如果 nums 中存在这个目标值 target ，则返回 true ，否则返回 false 。

你必须尽可能减少整个操作步骤。

示例 1：

输入：nums = [2,5,6,0,0,1,2], target = 0
输出：true

示例 2：

输入：nums = [2,5,6,0,0,1,2], target = 3
输出：false

提示：

1 <= nums.length <= 5000
-10⁴ <= nums[i] <= 10⁴
题目数据保证 nums 在预先未知的某个下标上进行了旋转
-10⁴ <= target <= 10⁴

进阶：

此题与搜索旋转排序数组相似，但本题中的 nums 可能包含重复元素。这会影响到程序的时间复杂度吗？会有怎样的影响，为什么？

lightbulb

解题思路

方法一：二分查找

我们定义二分查找的左边界 $l = 0$ ，右边界 $r = n - 1$ ，其中 $n$ 为数组的长度。

每次在二分查找的过程中，我们会得到当前的中点 $\textit{mid} = (l + r) / 2$ 。

如果 $\textit{nums}[\textit{mid}] > \textit{nums}[r]$ ，说明 $[l, \textit{mid}]$ 是有序的，此时如果 $\textit{nums}[l] \le \textit{target} \le \textit{nums}[\textit{mid}]$ ，说明 $\textit{target}$ 位于 $[l, \textit{mid}]$ ，否则 $\textit{target}$ 位于 $[\textit{mid} + 1, r]$ 。
如果 $\textit{nums}[\textit{mid}] < \textit{nums}[r]$ ，说明 $[\textit{mid} + 1, r]$ 是有序的，此时如果 $\textit{nums}[\textit{mid}] < \textit{target} \le \textit{nums}[r]$ ，说明 $\textit{target}$ 位于 $[\textit{mid} + 1, r]$ ，否则 $\textit{target}$ 位于 $[l, \textit{mid}]$ 。
如果 $\textit{nums}[\textit{mid}] = \textit{nums}[r]$ ，说明元素 $\textit{nums}[\textit{mid}]$ 和 $\textit{nums}[r]$ 相等，此时无法判断 $\textit{target}$ 位于哪个区间，我们只能将 $r$ 减少 $1$ 。

二分查找结束后，如果 $\textit{nums}[l] = \textit{target}$ ，则说明数组中存在目标值 $\textit{target}$ ，否则说明不存在。

时间复杂度 $O(n)$ ，其中 $n$ 为数组的长度。空间复杂度 $O(1)$ 。

我们定义二分查找的左边界 $l=0$ ，右边界 $r=n-1$ ，其中 $n$ 为数组的长度。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

class Solution:
    def search(self, nums: List[int], target: int) -> bool:
        n = len(nums)
        l, r = 0, n - 1
        while l < r:
            mid = (l + r) >> 1
            if nums[mid] > nums[r]:
                if nums[l] <= target <= nums[mid]:
                    r = mid
                else:
                    l = mid + 1
            elif nums[mid] < nums[r]:
                if nums[mid] < target <= nums[r]:
                    l = mid + 1
                else:
                    r = mid
            else:
                r -= 1
        return nums[l] == target

speed

复杂度分析

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

psychology

面试官常问的追问

外企场景

question_mark
Expect discussion on handling duplicates during binary search in rotated arrays.
question_mark
Check for clear reasoning about deciding which half is sorted despite rotations.
question_mark
Notice whether candidate handles worst-case linear scan scenario due to identical elements.

warning

常见陷阱

外企场景

error
Failing to handle duplicates correctly, leading to infinite loops or missed targets.
error
Assuming strictly increasing array properties, which breaks with repeated elements.
error
Overcomplicating the rotation logic instead of shrinking the search space carefully.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Search in Rotated Sorted Array without duplicates, which simplifies the binary search logic.
arrow_right_alt
Find the minimum element in a rotated sorted array with duplicates.
arrow_right_alt
Count occurrences of a target in a rotated sorted array allowing duplicates.

help

常见问题

外企场景

继续练习

#74 搜索二维矩阵 #35 搜索插入位置 #34 在排序数组中查找元素的第一个和最后一个位置