DevOps NetworkDevOpsNetwork
Join Free
DSA patterns

Search in Rotated Sorted Array

mediumBinary search Must-do

Problem statement

An array of distinct integers was sorted in ascending order and then rotated: some number of elements were moved from the front to the back, keeping their order. For example, [3, 6, 9, 12, 15, 18, 22] rotated by four becomes [15, 18, 22, 3, 6, 9, 12]. The rotation amount is unknown and may be zero.

Given the rotated array nums and a target, return the index of target, or -1 if it is not present. Aim for O(log n) time.

Examples

Example 1

Input: nums = [15, 18, 22, 3, 6, 9, 12], target = 6

Output: 4

Explanation: 6 is at index 4, in the part after the rotation point.

Example 2

Input: nums = [15, 18, 22, 3, 6, 9, 12], target = 20

Output: -1

Explanation: 20 is not in the array.

Hints

Approach

Run one binary search, and at each step decide which half is sorted.

  1. Set lo = 0, hi = len(nums) - 1.
  2. While lo <= hi, compute mid. If nums[mid] == target, return mid.
  3. If nums[lo] <= nums[mid], the left half [lo, mid] is sorted:
    • if nums[lo] <= target < nums[mid], the target can only be there: hi = mid - 1;
    • otherwise search the right: lo = mid + 1.
  4. Otherwise the right half [mid, hi] is sorted:
    • if nums[mid] < target <= nums[hi], go right: lo = mid + 1;
    • otherwise go left: hi = mid - 1.
  5. Return -1 when the range empties.

Every step discards half the range, exactly like ordinary binary search.

ComplexityTime O(log n)Space O(1)
Python
class Solution:
def search(self, nums: list[int], target: int) -> int:
lo, hi = 0, len(nums) - 1
while lo <= hi:
mid = lo + (hi - lo) // 2
if nums[mid] == target:
return mid
if nums[lo] <= nums[mid]: # left half is sorted
if nums[lo] <= target < nums[mid]:
hi = mid - 1
else:
lo = mid + 1
else: # right half is sorted
if nums[mid] < target <= nums[hi]:
lo = mid + 1
else:
hi = mid - 1
return -1

Follow-up questions

  • The array may now contain duplicates. What breaks, and what is the worst-case time?

Frequently asked questions

When lo == mid (a range of one or two elements), the left half is the single element nums[lo], which is trivially sorted. Using < would wrongly treat it as unsorted and can skip the target, for example searching [3, 1] for 3.

Yes. Find the index of the minimum with one binary search (see Find Minimum in Rotated Sorted Array), then binary-search whichever side can contain the target. It is also O(log n) and some people find it easier to get right.

Circular buffers and ring-based log storage: records are written in order, but the oldest one is not at index 0 once the buffer wraps. Searching one by timestamp is this problem.