LeetCode： 33. Search in Rotated Sorted Array

はじめに

転職も見据えて、LeetCodeをコツコツ解いていくことにした。
解くだけでは定着しそうにないので、格闘したLeetCodeの問題をメモしていく。

問題

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.

もともと昇順でソートされたListを何回か回転させる。その後、ある値targetを持つ要素は先頭から数えて何番目かを返す。
オーダーはO(log n)でなければならない

考え方

・オーダーの制約的にforで頭から数えるのは無理。
・2分探索で走査してO(log n)に収める

ポイント

・2分探索範囲のleft rightをいい感じに移動させて絞っていく
・ただし2分探索ができるのは、ソートがかかっている箇所に対してのみなので、部分的にソートされている箇所を探しながら、その箇所に対してのみ2分探索をかけていく
・対象の値が存在しない場合、left、rightがそれぞれを抜かしてしまうので条件式をWhileに追加（気づけなかった。。。）

コード

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left = 0
        right = len(nums)-1

        cnt = 0
        while left <= right:

            mid = (right - left)//2 + left
            if nums[mid] == target:
                return mid 
            if nums[left] <= nums[mid]:
                if nums[left] <= target and target <= nums[mid]:
                    right = mid-1
                else:
                    left = mid+1
            else:
                if target > nums[mid] and nums[right] >= target:
                    left = mid+1
                else:
                    right = mid-1

            
        return -1