'''

class Solution(object):

```
def search(self, nums, target):
start = 0
end = len(nums)
while start < end:
mid = (end+start)//2
if nums[mid] == target:
return mid
if (((nums[mid] >= nums[0]) == (target >= nums[0])) and target < nums[mid]) or ((nums[mid] < nums[0]) and (target >= nums[0])):
end = mid
elif (((nums[mid] >= nums[0]) == (target >= nums[0])) and target > nums[mid]) or ((nums[mid] >= nums[0]) and (target < nums[0])):
start = mid+1
return -1
```

'''

Let nums = [a1,a2,...,an, b1, b2,...,bm], where:

- a1<a2<...<an
- b1<b2<...<bm
- bi < aj, for 0<i<m,0<j<n

Four situations could happen with nums[mid] and target:

- Both nums[mid] and target are in a or b, and target < nums[mid], then end = mid(search in the first half of nums)
- Both nums[mid] and target are in a or b, and target > nums[mid], then start = mid+1.(search in the last half of nums)
- nums[mid] is in b, target is in a, then end = mid.
- nums[mid] is in a, target is in b, then start = mid+1.