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.
Binary search doesn't actually require a sorted array — it requires that you can discard half at each step. Here the array is broken into two sorted runs, and the key observation is that at least one side of mid is always sorted. Identify which one, test whether the target lies inside its known range, and you've recovered the discard rule. Any problem where you can name a predicate that flips exactly once is binary-searchable.
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
Common pitfalls
Comparing nums[mid] with nums[hi] to detect rotation
if nums[mid] <= nums[hi]: # right half sorted
...if nums[lo] <= nums[mid]: # left half sorted
...Both framings can work, but they need matching range tests, and mixing one convention's branch with the other's bounds is the usual source of silent wrong answers. Pick the lo-anchored form and keep the comparisons consistent with it.
Using < in the sorted-half test
if nums[lo] < nums[mid]:
if nums[lo] <= nums[mid]:
When the window narrows to two elements, lo == mid, so a strict comparison declares the left half unsorted and sends the search down the wrong branch. Equality means a single-element left side — which is trivially sorted.
Testing the target range with the wrong strictness
if nums[lo] <= target <= nums[mid]: hi = mid - 1
if nums[lo] <= target < nums[mid]: hi = mid - 1
nums[mid] == target was already handled and returned above, so including mid in the range accomplishes nothing and muddies the invariant. The half you keep must exclude the position you've already ruled out.
Edge cases
Left half is always sorted → degenerates to plain binary search.
mid=0, left half [3] sorted; range tests still route correctly.