Why can't I use regular binary search for Search in Rotated Sorted Array?

Regular binary search assumes a fully sorted array. Rotations break this order, so you must check which half is sorted at each step.

How do I determine which side of the array is properly sorted?

Compare the start, middle, and end values. The half where start <= middle (or middle <= end) is sorted, guiding where the target may exist.

What is the time complexity for this pattern?

The modified binary search maintains O(log n) because each iteration halves the search space, despite rotation.

Can this approach handle arrays of length 1?

Yes, the binary search logic still applies. If the single element equals the target, return 0; otherwise, return -1.

What if the array contains duplicates?

Duplicates require extra checks to skip equal elements since the sorted-half detection may be ambiguous; otherwise, the pattern remains similar.

#33

Medium

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

LeetCode 题解工作台

搜索旋转排序数组

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

数组二分查找

题目描述

整数数组 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,5,6,7] 下标 3 上向左旋转后可能变为 [4,5,6,7,0,1,2] 。

给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。

你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。

示例 1：

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

示例 2：

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

示例 3：

输入：nums = [1], target = 0
输出：-1

提示：

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

lightbulb

解题思路

方法一：二分查找

我们使用二分，将数组分割成 $[left,.. mid]$ , $[mid + 1,.. right]$ 两部分，这时候可以发现，其中有一部分一定是有序的。

因此，我们可以根据有序的那一部分，判断 $target$ 是否在这一部分中：

若 $[0,.. mid]$ $[0, .. mi d]$ 范围内的元素构成有序数组：
- 若满足 $nums[0] \leq target \leq nums[mid]$ ，那么我们搜索范围可以缩小为 $[left,.. mid]$ ；
- 否则，在 $[mid + 1,.. right]$ 中查找；
若 $[mid + 1, n - 1]$ $[mi d + 1, n - 1]$ 范围内的元素构成有序数组：
- 若满足 $nums[mid] \lt target \leq nums[n - 1]$ ，那么我们搜索范围可以缩小为 $[mid + 1,.. right]$ ；
- 否则，在 $[left,.. mid]$ 中查找。

二分查找终止条件是 $left \geq right$ ，若结束后发现 $nums[left]$ 与 $target$ 不等，说明数组中不存在值为 $target$ 的元素，返回 $-1$ ，否则返回下标 $left$ 。

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

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

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

speed

复杂度分析

指标	值
时间	complexity is O(log n) because each step halves the search space, and space complexity is O(1) if iterative, or O(log n) if recursion is used for binary search.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Ask why a standard binary search fails on rotated arrays.
question_mark
Probe understanding of identifying sorted segments versus pivoted segments.
question_mark
Check if candidate can maintain O(log n) efficiency despite rotation.

warning

常见陷阱

外企场景

error
Attempting simple binary search without handling rotation leads to incorrect indices.
error
Failing to correctly identify which half is sorted can skip the target unintentionally.
error
Overlooking edge cases where the pivot is at the array start or end causes off-by-one errors.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Searching in a rotated sorted array with duplicate values requires additional checks to skip equal elements.
arrow_right_alt
Finding the minimum element index in a rotated array leverages similar pivot detection logic.
arrow_right_alt
Counting occurrences of a target in a rotated sorted array extends the pattern to handle multiple identical elements.

help

常见问题

外企场景

继续练习

#34 在排序数组中查找元素的第一个和最后一个位置 #35 搜索插入位置 #4 寻找两个正序数组的中位数