Search in Rotated Sorted Array

Regular binary search falls apart the moment the array stops being fully sorted, and a rotated array looks exactly like that broken case. It isn't. Rotate a sorted array at some pivot and you get two sorted runs stitched together, so whichever midpoint you pick, one side is always a clean sorted stretch. Find that side, ask whether the target sits inside its range, and throw the other half away, all for the same O(log n) with one extra branch.