image.png

image.png

思路

這題題中說明是升序數(shù)組經(jīng)過了旋轉(zhuǎn)得到，我們可以找到它的旋轉(zhuǎn)點 O(n)
然后根據(jù)旋轉(zhuǎn)點 數(shù)組頭的值 數(shù)組尾的值我們可以確定在哪個區(qū)間使用二分查找 這樣劃出來的區(qū)間都是單調(diào)的 可以二分O(logn)
總的看是O(n)

實現(xià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: # 上面找不到說明是按頭或尾轉(zhuǎn)的
                if first>last: # 逆序
                    pivor = 0
                else:
                    pivor = nums_len-1
        print(pivor)
        # 根據(jù)轉(zhuǎn)點和頭尾判斷在哪個區(qū)間用二分
        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
        

優(yōu)化

二分思想 當(dāng)一個mid確定時 l-mid mid-r必會有一個單調(diào),我們只需要討論清楚target的取值范圍會落到哪個區(qū)間以此二分即可，這樣是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