Leetcode 33.回転ソート配列の検索(Search in Rotated Sorted Array)

Leetcode 33.回転ソート配列の検索
1タイトル記述(Leetcodeタイトルリンク)
  は、昇順に並べられた配列が予め未知の点で回転したと仮定する.(例えば配列[0,1,2,4,5,6,7]は[4,5,6,7,0,1,2]になる可能性がある).指定したターゲット値を検索し、配列にターゲット値が存在する場合はインデックスを返します.そうでない場合は-1を返します.配列に重複する要素が存在しないと仮定できます.あなたのアルゴリズムの時間複雑度はO(log n)レベルでなければなりません.

  : nums = [4,5,6,7,0,1,2], target = 0
  : 4

  : nums = [4,5,6,7,0,1,2], target = 3
  : -1

2問題解
  本題は153番と似ていますが、153番より判断することが多いです.

中点がtargetに等しいかどうかを判断し、等しい場合は直接中点下標に戻る.

果中点が右値より小さい場合、右半分は必ず第2の昇順配列にあり、この場合、targetが中点と右値の間にある場合、二分は右半分を判断し、逆に左半分を判断する.

中点が右値より大きい場合、左半分は必ず第1の昇順配列にあり、この場合、targetが左値と中点の間にある場合、二分は左半分を判断し、逆に右半分を判断する.

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        if not nums:
            return -1
        length = len(nums)
        left, right = 0, length - 1
        while left <= right:
            mid = (left + right) // 2
            if nums[mid] == target:
                return mid
            if nums[mid] < nums[right]:
                if target > nums[mid] and target <= nums[right]:
                    left = mid + 1
                else:
                    right = mid - 1
            else:
                if target < nums[mid] and target >= nums[left]:
                    right = mid - 1
                else:
                    left = mid + 1
        return -1