ローテーションされたソート済みリストから最小の要素を見つける

問題

今日はFind the minimum element in a sorted and rotated arrayの問題。ソートとローテーションされたリストから最小の要素を見つける問題。ローテーション回数はわかりません。

input: [5,6,1,2,3,4]
output: 1

実装

ポイントは最小の要素は、1個前の要素が、その要素よりも大きいという区切りを見つけること。[5,6,1,2,3,4] というリストの場合、[5 > 6] はFalse、[6 > 1] はTrue、[1 > 2] はFalseとなるので、そのような区切りを見つけることが、最小の要素を見つけることになる。

最小の要素が中央にない場合、最小の要素は左半分または右半分のいずれかにあるので、中央の要素が最後の要素よりも小さい場合、最小の要素は左半分にあり、それ以外であれば最小要素は右半分にあることがわかります。

from typing import List

def findMin(numbers: List[int]) -> int:
    low = 0
    high = len(numbers) - 1

    while low < high:
        mid = (low + high) // 2

        if numbers[mid] == numbers[high]:
            high -= 1
        elif numbers[mid] > numbers[high]:
            low = mid + 1
        else:
            high = mid
    return numbers[high]

numbers = [6, 2, 3, 4, 5]
print(findMin(numbers))

numbers = [3, 4, 5, 6, 2]
print(findMin(numbers))

numbers = [3, 4, 5, 2, 2]
print(findMin(numbers))

numbers = [2,3,4,5,6]
print(findMin(numbers))

2
2
2
2