Search a rotated sorted array

A sorted array has been rotated at some unknown pivot — [7, 9, 1, 3, 5], say. Find the index of a target value in O(log n), or report that it is absent.

The invariant to articulate: at every step, at least one half of the current range is still sorted. Say how you determine which, and what you do with that.