Divide the array into 2 parts `left` and `right`. Since this array is
rotated sorted, elements in left is always bigger than elements in right.

Let's choose the middle of this array. The middle element should be either in
`left` or in `right`. If `mid` is in left, then it must be greater than
`max(right) = right[-1]`, and we could simply judge whether the target is in
its left or right. And if `mid` is in right, it must be smaller than
`right[-1]`. And we could also simply judge whether the target is in its
right.

```
class Solution:
def search(self, nums: List[int], target: int) -> int:
lo = 0
hi = len(nums) - 1
while hi >= lo:
mid = (lo + hi) // 2
if nums[mid] == target:
return mid
if nums[lo] <= nums[mid]:
if nums[lo] <= target < nums[mid]:
hi = mid - 1
else:
lo = mid + 1
else:
if nums[mid] < target <= nums[hi]:
lo = mid + 1
else:
hi = mid - 1
return -1
```