Find In Rotated Sorted Array

A sorted (ascending) array of distinct values has been rotated at an unknown pivot. Return the index of target, or -1 if absent, in O(log n).

searchRotated(nums, target)

Input format: nums | target.

Examples

[4, 5, 6, 7, 0, 1, 2], target=0   // → 4
[4, 5, 6, 7, 0, 1, 2], target=3   // → -1
[1], target=1                     // → 0

Walkthrough

Thinking it through

A rotated array seems to break binary search — comparing the target to the middle doesn't tell you which half to search the usual way. But the array is exactly two contiguous sorted runs (the tail of the original wrapped to the front). That structure is what makes binary search still possible.

The key observation

At any step, look at [lo, mid]. Either this left portion is properly sorted, or the rotation break is inside it, forcing [mid, hi] to be sorted instead. One comparison tells you which: if nums[lo] <= nums[mid], the left portion is sorted (a rotation break inside it would force nums[lo] > nums[mid]). Otherwise, the right portion is sorted.

Using the sorted half to decide direction

Once you know which half is sorted, check whether the target could fall within its value range. If so, search there — the target definitely isn't in the other, unsorted-looking half. If not, search the other half instead.

Either way, one comparison discards half the current range, just like standard binary search — the only extra step is figuring out which half is safe to reason about first.

Why this beats scanning, and why it still works despite the rotation

A linear scan takes time proportional to the array's length. This approach preserves binary search's core guarantee — eliminating half the range each comparison — since even though the whole array isn't sorted, at least one half always is, and that's enough for a safe halving decision every step.

main.py

Auto-saved

Console

Press Run to execute your code, or Submit to test and complete this problem.