Search in a Rotated Sorted Array

A sorted list of distinct numbers was rotated at an unknown point, e.g. [4, 5, 6, 7, 0, 1, 2]. Find a target's index in $O(\log n)$, or -1 if it's missing.

At each binary-search step, at least one half is still sorted. Check whether the target falls inside that half to decide which way to go.

Implement search_rotated(nums, target) and find_rotation(nums), which returns the index of the smallest element (0 if not rotated).