leetcode 33. Search in Rotated Sorted Array

  • 2022-07-16 11:52:55

In order to help me understand all the possible situations I should consider, I just draw a picture to make everything easier.
So acutally there are four situations we should consider, we should first see where middle pointer points at, and then consider whether target is in the left part or right part
leetcode 33. Search in Rotated Sorted Array

class Solution(object):
    def search(self, nums, target):
        start = 0
        end = len(nums) - 1
        while start <= end:           
            middle = (start + end) // 2
            if nums[middle] == target: # if we find target
                return middle
            if nums[middle] > nums[end]: # in situation 1
                if target >= nums[start] and target < nums[middle]: # target in left part in situtation 1 
                    if target == nums[start]: return start
                    end = middle - 1
                else: # target in right part in situation 1
                    start = middle + 1
                    if start >= len(nums):
                        return -1
            else:# in situation 2
                if target >= nums[middle] and target <= nums[end]: # target in right part in situation 2
                    if target == nums[end]: return end
                    start = middle + 1
                else: # target in left part in situation 2
                    end = middle - 1
                    if end < 0:
                        return -1
        return -1 
        

 

猜你喜欢