今天是紀錄LeetCode解題的第三十三天

第三十三題題目：There is an integer array nums sorted in ascending order (with distinct values).

Prior to being passed to your function, nums is possibly left rotated at an unknown 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 left rotated by 3 indices 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.

有一個nums按升序排序的整數數組（具有不同的值），在傳遞函數之前，nums可能在索引處k左旋轉，導致數組變成[nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (從索引0開始)，例如：
[0,1,2,4,5,6,7]在索引三處左旋轉變成[4,5,6,7,0,1,2]

給定一個旋轉後的數組和整數target，回傳target在nums中的索引，如果target不存在於nums中則回傳-1

時間複雜度須為O(log n)

解題思路

設left = 0、right = len(nums)-1，算出中點mid，判斷哪一半是排序好的，根據target落在左半邊還是右半邊，縮小搜尋區間

程式碼

class Solution:
    def search(self, nums: List[int], target: int) -> int:       
        left, right = 0, len(nums) - 1
        while left <= right:
            mid = (left + right) // 2 #計算中點

            if nums[mid] == target: #如果找到target直接回傳
                return mid

            #左半邊是排序好的
            if nums[left] <= nums[mid]:
                if nums[left] <= target < nums[mid]:
                    right = mid - 1
                else:
                    left = mid + 1
            #右半邊是排序好的
            else:
                if nums[mid] < target <= nums[right]:
                    left = mid + 1
                else:
                    right = mid - 1
        return -1

        '''if target in nums: #這種寫法可以通過這題，但不符合時間複雜度O(log n)
            return nums.index(target)
        else:
            return -1'''

初始狀態

• nums = [4,5,6,7,0,1,2]
• target = 3
• left = 0
• right = 6

第一次執行

• mid = (left + right) // 2 = 3
• nums[left] <= nums[mid] → 4 <= 7 → True
• nums[left] <= target < nums[mid] → 4 <= 3 < 7 → False
• left = mid + 1 = 4

第二次執行

• mid = (left + right) // 2 = (4 + 6) // 2 = 5
• nums[left] <= nums[mid] → 0 <= 1 → True
• nums[left] <= target < nums[mid] → 0 <= 3 < 1 → False
• left = mid + 1 = 6

第三次執行

• mid = (left + right) // 2 = (6 + 6) // 2 = 6
• nums[left] <= nums[mid] → 2 <= 2 → True
• nums[left] <= target < nums[mid] → 2 <= 2 < 2 → False
• left = mid + 1 = 7

最後left = 7 > right = 6 → 跳出迴圈回傳-1表示沒找到target在nums中的索引