python 12-line solution with binary search


  • 0
    S

    '''
    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.

Log in to reply
 

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