Search in Rotated Sorted Array

Search for a target value in a rotated sorted array (an array that was sorted then rotated at some pivot). Return the index of the target, or -1 if not found.

Example

search_rotated([4, 5, 6, 7, 0, 1, 2], 0)
# => 4
search_rotated([4, 5, 6, 7, 0, 1, 2], 3)
# => -1