33. Search in Rotated Sorted Array

33. Search in Rotated Sorted Array
33. Search in Rotated Sorted Array
1o 若target在A与D之间,要么位于AB之间,要么位于CD之间,那么当target在A-min1或者mid2-D之间是确定的二分查找,当在mid1-mid2之间就是和原来问题相同的子问题,递推即可,找得到下标就证明存在,找到最后都没找到,就证明不存在。
2o 若target不在A与D之间,那肯定就在AD之间时找不到。
33. Search in Rotated Sorted Array

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        low = 0
        high = len(nums)-1
        while low <= high:
            mid = (low+high) // 2
            if nums[mid] == target:
                return mid
            if nums[mid] < nums[high]:
                if nums[mid] < target and target <= nums[high]:
                    low = mid + 1
                else:
                    high = mid - 1
            else:
                if nums[mid] > target and target >= nums[low]:
                    high = mid - 1
                else:
                    low = mid + 1
        return -1                                            

33. Search in Rotated Sorted Array
进阶:Search in Rotated Sorted Array II

猜你喜欢