Binary Search on a Rotated Sorted Array

A sorted array cyclically rotated by some unknown amount still hides enough order to binary-search it in $\Theta(\log n)$: there is exactly one "drop" where $A[i]>A[i+1]$, and at every midpoint one half is guaranteed sorted, so you can find the pivot, the minimum, the maximum, or any target in logarithmic time.