Binary Search — Search in a Rotated Sorted Array

nums was sorted in ascending order, then rotated at an unknown pivot:
[0, 1, 2, 4, 5, 6, 7] may have become [4, 5, 6, 7, 0, 1, 2]. All values
are distinct. Return the index of target, or -1 if it is absent.

The requirement is O(log n). At every step of the binary search, at least
one half, [low..mid] or [mid..high], is still sorted. Check whether the
target lies inside the sorted half; if it does, search there, otherwise search
the other half.

Examples

solve([4, 5, 6, 7, 0, 1, 2], 0)  → 4
solve([4, 5, 6, 7, 0, 1, 2], 3)  → -1
solve([1], 0)                    → -1

Constraints

• 1 <= nums.length <= 5000, all values distinct
• The array may also not be rotated at all.