How do you search in a rotated sorted array?

Short answer: Modified binary search: check which half is sorted, then decide whether the target lies in that sorted half. Still O(log n).

Interview approach

1. Compute mid.
2. If left half sorted (nums[lo] ≤ nums[mid]): if target in [lo, mid) go left else right.
3. Else right half sorted: if target in (mid, hi] go right else left.

Complexity

Time O(log n), Space O(1).

Edge cases to mention

• No rotation
• Duplicates (harder — may degrade to O(n))
• Single element

Draw a rotated array and mark the sorted half each step while explaining.