題目:

There is an integer array nums sorted in ascending order (with distinct values).

Prior to being passed to your function, nums is possibly rotated at an unknown pivot index k (1 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (0-indexed). For example, [0,1,2,4,5,6,7] might be rotated at pivot index 3 and become [4,5,6,7,0,1,2].

Given the array nums after the possible rotation and an integer target, return the index of target if it is in nums, or -1 if it is not in nums.

You must write an algorithm with O(log n) runtime complexity.

給定一陣列,該陣列由一升序陣列,值都是獨一無二的,將其前段一部分移至後方構成
ex:[4,5,6,7,0,1,2]為[0,1,2]移到後方構成
題目給定一數(target),若target在陣列內回傳其index,反之回傳-1
限制時間複雜度為O(log n)

題目限制O(log n),第一時間想到二分搜
但這題是比較tricky的二分搜

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        
            
        if nums[-1]==target: #若target即為nums[-1],回傳len(nums)-1
            return len(nums)-1
        
        if nums[0]>target and nums[-1]<target: #若target位於nums[0]和nums[-1]之間,表示target不在該陣列,回傳-1
            return -1
        
        l=0
        r=len(nums)-1
            
        if nums[-1]>target:
            while l<r:
                mid=(l+r)//2
                if nums[mid]>target and nums[mid]<nums[-1]:
                    r=mid-1
                elif nums[mid]==target:
                    return mid
                else:
                    l=mid+1
                     
        else:
            while l<r:
                mid=(l+r)//2
                if nums[mid]<target and nums[mid]>nums[-1]:
                    l=mid+1
                elif nums[mid]==target:
                    return mid
                else:
                    r=mid-1
                    
                    
        if nums[l]==target:
            return l
        else:
            return -1

根據經驗,二分搜常用於排序陣列,但這題的輸入並不是
為了讓我們能運用二分搜
我們可以將題目給的陣列分為兩個部分,被移到後方的部分(s2)和其餘的部分(s1)
以 [4,5,6,7,0,1,2]為例,[4,5,6,7]為s1,[0,1,2]為s2
也就是兩個排序陣列
而我們知道s2元素小於s1的任何元素(因為它們原本是一升序排列的陣列)

我發現可以用陣列最後一數來判斷target會位在s1還是s2
最後一數身為s2最大的數,第一數身為s1最小的數
若target位於nums[0]和nums[-1]之間,表示target不在該陣列,回傳-1
其餘若target大於nums[-1],則target會在s1
若target小於nums[-1],則target會在s2

正常分兩種狀況,target在s1和target在s2
設下限l=0跟上限r=len(nums)-1,mid定義為(1+r)//2

target在s2:
和一般二分搜的作法差不多,但有個特例要注意
若nums[mid]>target但nums[mid]位在s1內
照理來說nums[mid]>target我們應該要把r邊界往下移
但我們已知target在s2,而此時mid在s1內
表示從l到mid這段全部都是s1的範疇,target不可能在這裡
所以我們反倒要將l邊界往上移去除這塊區域

target在s1:
同樣有個類似特例要注意
若nums[mid]< target但nums[mid]位在s2內
一般nums[mid]< target我們應該要把l邊界往上移
但我們已知target在s1,而此時mid在s2內
表示從mid到r這段全部都是s2的範疇,target不可能在這裡
所以我們反倒要將r邊界往下移去除這塊區域

二分搜到最後都沒有mid回傳的話
則檢測l位置的值是否為target
是的話回傳l,不是的話表示target不在此陣列內,回傳-1
最後執行時間41ms(faster than 96.03%)

那我們下題見