33. Search in Rotated Sorted Array

Rotation breaks the array into two sorted runs, but here's the invariant that saves you: when you split at mid, at least one of the halves [left, mid] or [mid, right] is still fully sorted. Identify…