#33

Medium

auto_awesomeBinary search over the valid answer space

LeetCode Problem Workspace

Search in Rotated Sorted Array

Find the index of a target in a rotated sorted array using a careful binary search that handles pivot shifts.

Problem Statement

You are given an integer array nums that was originally sorted in ascending order but might have been rotated at an unknown pivot. The rotation shifts elements so that the array may look like [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]].

Given this possibly rotated array nums and an integer target, return the index of target if it exists in nums; otherwise, return -1. Your solution must efficiently search without scanning every element.

Examples

Example 1

Input: nums = [4,5,6,7,0,1,2], target = 0

Output: 4

Example details omitted.

Example 2

Input: nums = [4,5,6,7,0,1,2], target = 3

Output: -1

Example details omitted.

Example 3

Input: nums = [1], target = 0

Output: -1

Example details omitted.

Constraints

1 <= nums.length <= 5000
-104 <= nums[i] <= 104
All values of nums are unique.
nums is an ascending array that is possibly rotated.
-104 <= target <= 104

Solution Approach

Identify Sorted Half

At each binary search step, determine whether the left or right half of the current segment is sorted. This ensures you can rule out halves where the target cannot reside, respecting the rotated structure.

Adjust Search Range

Compare the target to the sorted half's boundaries. If the target lies within this half, continue the search there; otherwise, shift to the other half. Repeat until the target is found or the search space is empty.

Return Result

If the search concludes without locating the target, return -1. Otherwise, return the index identified during binary search, ensuring correctness even when the pivot divides the array.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time 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.

What Interviewers Usually Probe

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

Common Pitfalls or Variants

Common pitfalls

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

Follow-up variants

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

FAQ

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.

terminal

Solution

Solution 1: Binary Search

We use binary search to divide the array into two parts, $[left,.. mid]$ and $[mid + 1,.. right]$. At this point, we can find that one part must be sorted.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

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

Continue Practicing

#34 find first and last position of element in sorted array #35 search insert position #4 median of two sorted arrays