Python ugly long code but easy to understand, and accepted 38ms


  • 0
    P
    class Solution(object):
        def search(self, nums, target):
            """
            :type nums: List[int]
            :type target: int
            :rtype: int
            """
    #find the rotate point - binary search
            if len(nums) == 1:
            	return 0 if nums[0] == target else -1
            lv, rv = nums[0], nums[-1]
           	l, r = 0, len(nums)-1
            if lv > rv:
    	        mid = (l+r)//2
    	        while r >= l:
    	        	if nums[mid] >= lv:
    	        		l = mid + 1
    	        	if nums[mid] <= rv:
    	        		r = mid - 1
    	        	mid = (l+r)//2
            l, r = r, l
    
    # get the new search range
            if target > nums[0]:
            	l, r = 0, l
            elif target < nums[-1]:
            	l, r = r, len(nums)-1
            elif target == nums[0]:
            	return 0
            elif target == nums[-1]:
            	return len(nums)-1
            else:
            	return -1
    
    # search for the result - binary search again       	
            mid = (l+r)//2
            while r > l:
            	if nums[mid] < target:
            		l = mid + 1
            	elif nums[mid] > target:
            		r = mid - 1
            	else:
            		return mid
            	mid = (l+r)//2
    
            if nums[l] != target:
            	return -1
            else:
            	return l
    

Log in to reply
 

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