Problem editorialmedium
Search a rotated sorted array
Rotation breaks global order in exactly one place — so around any midpoint one half is always still sorted. That surviving structure is all binary search needs.
18 min read·time O(log n)·space O(1)
Half-sorted invariantTwo-layer decisionPivot