NeetCode 150 [BinarySearch]:easy 4/5

NeetCodeのSolutionを書いていく

Search in Rotated Sorted Array

問題

長さnの配列が与えられます。もともと昇順でソートされていたものです。
今、1~nの間で回転されました。
一緒に整数targetが与えられます。
targetのindexか、存在しない場合は-1を返しなさい。
numsの要素はユニークです。
計算量O(n)の回答では当たり前過ぎます。O(logn)でできますか？

制約

• 1 <= nums.length <= 1000
• -1000 <= nums[i] <= 1000
• -1000 <= target <= 1000

計算量：O(logn)
メモリ：O(1)

例

Input: nums = [3,4,5,6,1,2], target = 1
Output: 4

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

メモ

前回の問題と似ていそう。

from typing import List


class Solution:
    def search(self, nums: List[int], target: int) -> int:
        # ローテーションすると、最初の状態(0回ローテーション)以外で、昇順ソートされた配列が２つ存在する状態になる。
        # 配列の一番左をl、右をr、真ん中をmとする。
        # この時 target == nums[l]ならlをtarget == nums[m]ならmをtarget == nums[r]ならrを返す。
        # nums[l] > nums[m] の場合、lとmは異なるソート配列に存在する。
        #   この時target < nums[m] の場合は、l~mにtargetが存在する可能性があるので、rをmにする。
        #   そうではない場合で、nums[m] < target < nums[r] の場合は m~rにtargetが存在する可能性があるので、lをmにする。
        #   それ以外の場合はtargetは存在しないので-1を返す。
        # それ以外の場合は、lとmは同じソート配列に存在する。
        #   この時 nums[l] < target < nums[m]の場合は、l~mにtargetが存在する可能性があるので、rをmにする。
        #   そうではない場合は、m~rにtargetが存在する可能性があるので、lをmにする。
        # mを(l+m)//2にする。
        # 上記を繰り返す

        l = 0
        r = len(nums) - 1
        while l <= r:
            m = (l + r) // 2

            if target == nums[l]:
                return l
            elif target == nums[m]:
                return m
            elif target == nums[r]:
                return r

            if nums[l] > nums[m]:
                if nums[m] < target and target < nums[r]:
                    l = m + 1
                else:
                    r = m - 1
            else:
                if nums[l] < target and target < nums[m]:
                    r = m - 1
                else:
                    l = m + 1

        return -1