NeetCode 150 [Binary Search]:easy 3/5

NeetCodeのSolutionを書いていく

Find Minimum In Rotated Sorted Array

問題

長さnの配列が与えられます。
もともとは昇順ソートされていたものです。
1~n回のローテーションがされています。
例えば[1,2,3,4,5,6]は4回ローテーションすると[3,4,5,6,1,2]、6回ローテーションすると[1,2,3,4,5,6]になります。
4回ローテーションすると最後の4つの要素が最初に移動します。6回ローテーションすると最初と同じになります。
numsの要素はユニークとする時の最小の要素を返しなさい。
計算量がO(n)のアルゴリズムができるのは当然です。O(logn)出できますか？

制約

• numsの長さは1以上1000以下
• numsの要素は-1000以上1000以下

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

例

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

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

Input: nums = [4,5,6,7]
Output: 4

メモ

もともとソートされている配列なので、ローテーションするとソートされた２つの配列になる。
ソートの切れ目に最小値がある。
配列の左端l右端r真ん中mを考えた時

nums[l] < nums[m] であれば左の配列はソート済み、
この時nums[m] < nums[r]であれば右の配列もソート済みなので最小値はnums[0]
そうでない場合は、m~rの間に最小値がある。nums[m]とnums[r]の値から最小値を保持しておく
l=m, m=(l+r)//2として繰り返す
l==mとなったら処理終了
そうでない場合は左の配列はソートされていない(ソートの切れ目がある)のでl~mの間に最小値がある
nums[l]とnums[m]の最小値を保持しておく
r = m, m=(l+r)//2として繰り返す
r == m となったら処理終了

徐々に探索範囲を半分にするのでO(logn)最小値を保持するためのメモリがO(1)

from typing import List


class Solution:
    def findMin(self, nums: List[int]) -> int:
        l = 0
        r = len(nums) - 1
        m = (l + r) // 2

        while True:
            mv = min(nums[m], nums[r])
            if nums[l] < nums[m]:
                if nums[m] < nums[r]:
                    return nums[0]
                l = m
            else:
                r = m

            m = (l + r) // 2
            if l == m or r == m:
                return mv