Search in Rotated Sorted Array
Find a target index in a rotated sorted array with distinct values.
Why does this pattern fit?
Restate the exact job
Find a target index in a rotated sorted array with distinct values.
At least one half around mid is normally sorted.
O(log n) time · O(1) space
Comparing only target with mid ignores the rotation.
How to solve Search in Rotated Sorted Array
The goal is to solve this problem from the pattern, not to memorize a finished answer. Use this as a check after your own attempt.
What the question asks
Find a target index in a rotated sorted array with distinct values.
Why Binary search fits
At least one half around mid is normally sorted.
State to maintain
An inclusive candidate interval.
Transition
Identify the sorted half; keep it only if the target lies within its bounds.
Time and space
O(log n) time · O(1) space
Counterexample to the tempting mistake
Comparing only target with mid ignores the rotation.
Prove it again tomorrow
Close this page. Rebuild the state and transition from memory, write a test that exposes the mistake above, then solve a fresh input without looking back. A same-day reread is practice, not proof of retention.