Search in Rotated Sorted Array

Problem

Given an integer array nums sorted in ascending order (with distinct values) that has been possibly rotated at an unknown pivot, and an integer target, return the index of target if it is in nums, or -1 if it is not. You must write an algorithm with O(log n) runtime complexity.

Example 1

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

Output: 4

Explanation: 0 is found at index 4. Right half [0,1,2] is sorted; target lies within it.

Example 2

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

Output: -1

Explanation: 3 is not present in the array.

Example 3

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

Output: 5

Explanation: 4 is found at index 5. Right half [0,1,2,4,5] is sorted; target is in range.

Constraints: 1 ≤ nums.length ≤ 5000 | −10⁴ ≤ nums[i], target ≤ 10⁴ | All values distinct

Array

target —

Variables

—

mid

—

nums[lo]

—

nums[mid]

—

nums[hi]

—

Step Logic

Press ▶ Play or Next Step to begin the animation.

Ready

0 / 0

Select an example above and press Play.

Algorithm

In a rotated sorted array, one half is always sorted

Compute mid; check if left half is sorted: nums[lo] ≤ nums[mid]

Left sorted: if target ∈ [nums[lo], nums[mid]) → go left (hi = mid − 1)

Left sorted: otherwise target is in right half → go right (lo = mid + 1)

Right sorted: if target ∈ (nums[mid], nums[hi]] → go right (lo = mid + 1)

Right sorted: otherwise target is in left half → go left (hi = mid − 1)

Return -1 if the loop ends without finding target

Time

O(log n)

Space

O(1)

Why It Works

Even after rotation, exactly one of the two halves [lo..mid] or [mid..hi] is guaranteed to be sorted in ascending order. By identifying which half is sorted, we can check in O(1) whether the target lies in that sorted range. If yes, we search there; if no, it must be in the other (rotated) half. This eliminates half the remaining elements each iteration, giving O(log n) total time — the same as standard binary search despite the rotation.