欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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