FAANG · LeetCode #33

Search in Rotated Sorted Array — three-stage drill

1The ProblemMedium

Search in Rotated Sorted Array

Find a target's index in a sorted array that's been rotated.

Examples

[5,6,7,0,1,2,4], t=4→ 6t=8→ -1

constraintDistinct values; the array is a sorted array rotated at one pivot.

2The PatternTIME O(log n) · SPACE O(1)

Binary Search

Halve the search space each step — check the middle, keep the half that can hold the answer.

Problems using this pattern

3The SolutionRESULT → 6

Step through it

rotated sorted array · target = 4 · left = 0, right = 6

Step 1 / 4

Python▎find the sorted half · is target in its range?

1def search(nums, target):
2    left, right = 0, len(nums) - 1
3    while left <= right:
4        mid = (left + right) // 2
5        if nums[mid] == target:
6            return mid
7        if nums[left] <= nums[mid]:           # left half sorted
8            if nums[left] <= target < nums[mid]:
9                right = mid - 1
10            else:
11                left = mid + 1
12        else:                                  # right half sorted
13            if nums[mid] < target <= nums[right]:
14                left = mid + 1
15            else:
16                right = mid - 1
17    return -1

why it worksEven rotated, one half [left..mid] or [mid..right] is always still in order. Find that sorted half and check whether the target lies within its value range: if so, search it; if not, the target must be in the other half. Still O(log n).

Arrow keys to navigate · escape to reset

All problems by pattern

Two Pointers

Sliding Window

Prefix Sum

Monotonic Deque

Shortest Subarray with Sum at Least K

Binary Search

Arrays & Hashing

Monotonic Stack

Intervals

Search in Rotated Sorted Array — three-stage drill