Search in Rotated Sorted Array
A sorted array was rotated at an unknown pivot. Find target's index in O(log n), or −1.
Intuition
Cut a rotated array anywhere and at least one half is still perfectly sorted. Check which half is sorted, and whether the target's value falls inside that half's range — that tells you which side to discard, so binary search survives the rotation.
Approach
One half is always sorted
If nums[lo] <= nums[mid], the left half is sorted; otherwise the right half is. The rotation point can only be on one side of mid.
Range-test the sorted half
A sorted half has known min and max. If the target lies in that range, search it; otherwise the target must be in the other (messy) half.
Loop as normal binary search
Each step still halves the space — same O(log n), just a smarter discard rule.
Solution & live demo
Edge cases
Left half is always sorted → degenerates to plain binary search.
mid=0, left half [3] sorted; range tests still route correctly.