image.png

image.png

思路

这题题中说明是升序数组经过了旋转得到，我们可以找到它的旋转点 O(n)
然后根据旋转点 数组头的值 数组尾的值我们可以确定在哪个区间使用二分查找 这样划出来的区间都是单调的 可以二分O(logn)
总的看是O(n)

实现

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        # 先找分割点
        nums_len = len(nums)
        pivor = 0
        first = nums[0]
        last =nums[0]
        for i in range(nums_len):
            if i-1>-1 and i+1<nums_len and nums[i-1]>nums[i] and nums[i]<nums[i+1]:
                pivor = i
                break
            if i == nums_len-1: # 上面找不到说明是按头或尾转的
                if first>last: # 逆序
                    pivor = 0
                else:
                    pivor = nums_len-1
        print(pivor)
        # 根据转点和头尾判断在哪个区间用二分
        left =0
        right =nums_len-1
        if target>=nums[0]:
            left = 0
            right = pivor # 左闭右闭
        else:
            left = pivor
            right =nums_len-1
        while(left<=right):
                mid = left+(right-left)//2
                if nums[mid]<target:
                    left=mid+1
                elif nums[mid]>target:
                    right=mid-1
                elif nums[mid]==target:
                    return mid
        return -1
        

优化

二分思想 当一个mid确定时 l-mid mid-r必会有一个单调,我们只需要讨论清楚target的取值范围会落到哪个区间以此二分即可，这样是O(logn)

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        # 直接去二分
        nums_len= len(nums)
        l,r = 0,nums_len-1 # 双闭
        while(l<=r):
            mid = l + (r-l)//2
            if (nums[mid]==target):
                return mid
            if nums[l]<=nums[mid]: # 说明 l-mid 有序
                if target<nums[mid] and target>=nums[l]: # 搜l-mid-1
                    r=mid-1
                elif target>nums[mid] or target<nums[l]: # 搜mid+1-r
                    l=mid+1
            else: # 说明 mid-r 有序
                if target>nums[mid] and target<=nums[r]: # 搜mid+1-r
                    l=mid+1
                elif target<nums[mid] or target>nums[r]: # 搜l-mid-1
                    r=mid-1

        return -1