Search in a Rotated Sorted Array

Difficulty: Medium · Pattern: Binary Search · Concept: General Coding (DSA) — Core Patterns to Drill

Find the Rotation Point located the minimum in a rotated sorted array. This problem is genuinely harder, not a rename: find a target value's index directly, in one $O(\log n)$ binary search — without first finding the rotation point as a separate step.

The key insight: at any mid, comparing arr[mid] to arr[lo] tells you which half is the normally-sorted one (the rotation point is only ever in one half or the other). Once you know which half is sorted, you can cleanly check whether the target falls inside that sorted half's range — and if it does, search there; if it doesn't, the target must be in the other half.

Your task: implement search_rotated(arr, target), returning the target's index, or -1 if it isn't present. arr has no duplicates.

Next: Longest Increasing Subsequence