# python 12-line solution with binary search

• '''
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:

1. Both nums[mid] and target are in a or b, and target < nums[mid], then end = mid(search in the first half of nums)
2. 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)
3. nums[mid] is in b, target is in a, then end = mid.
4. nums[mid] is in a, target is in b, then start = mid+1.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.