Search in Rotated Sorted Array
FreeBinary searchMedium18 of 75
The problem
Search for a target in a rotated ascending array of distinct integers. Return its index, or −1 if it is absent, using logarithmic time.
Example
nums = [6, 8, 10, 1, 3], target = 1 → 3
Need a hint?
At least one half around the midpoint is sorted.
Write pseudocode, trace the example, or note an edge case. This scratchpad does not run code.
Notes stay in this browser when storage is available.
Read the solution approach
Check the midpoint first. Identify the sorted half by comparing its endpoints. If the target lies within that half’s value range, search there; otherwise search the other half. Exclude mid after it has failed. Continue while left ≤ right.
Complexity
O(log n) time and O(1) space.
Before moving on, explain why the algorithm is correct and trace a boundary case without looking at the approach.