python怎么實現(xiàn)搜索旋轉(zhuǎn)排序數(shù)組

【題目】

假設(shè)按照升序排序的數(shù)組在預(yù)先未知的某個點上進行了旋轉(zhuǎn)。

( 例如，數(shù)組 [0,1,2,4,5,6,7] 可能變?yōu)?[4,5,6,7,0,1,2] )。

搜索一個給定的目標值，如果數(shù)組中存在這個目標值，則返回它的索引，否則返回 -1 。

你可以假設(shè)數(shù)組中不存在重復的元素。

你的算法時間復雜度必須是 O(log n) 級別。

示例 1:
輸入: nums = [4,5,6,7,0,1,2], target = 0
輸出: 4
    
示例 2:
輸入: nums = [4,5,6,7,0,1,2], target = 3
輸出: -1 

【思路】

1、暴力解法：for循環(huán)遍歷，找到目標值。

2、二分查找特殊變形。必須理解到：不管怎么旋轉(zhuǎn)，總有一部分區(qū)間是有序的。比如，l->mid和mid->r之中至少有一個是有序的。我們的邏輯就是：判斷target是否在有序區(qū)間中，在則將另一個指針移動到有序區(qū)間內(nèi)，否則將有序區(qū)間的指針（除mid外的另一個邊界指針）移動到有序區(qū)間外。

【代碼】

python版本

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        l, r = 0, len(nums) - 1
        while l <= r:
            mid = (l + r) // 2
            if nums[mid] == target:
                return mid
            
            # mid->r是有序的
            if nums[mid] < nums[r]:
                if nums[mid] < target <= nums[r]:
                    l = mid + 1
                else:
                    r = mid - 1
                    
            # l->mid是有序的
            else:
                if nums[l] <= target < nums[mid]:
                    r = mid - 1
                else:
                    l = mid + 1
        return -1