회전 정렬 그룹에서 최소값을 찾습니다

* 미리 모르는 축에서 오름차순으로 정렬된 배열이 회전한다고 가정합니다.
(즉, [0,1,2,4,5,6,7]는 [4,5,6,7,0,1,2]로 변할 수 있다).
최소 요소를 찾습니다.
배열에 중복 항목이 존재하지 않는다고 가정할 수 있습니다 *
예를 들면 -
"""
입력:[3,4,5,1,2]
산출: 1
"""
솔루션 -
가장 간단한 방법은 그룹을 교체해서 최소값을 찾는 것이다.

return min(arr)

이것은 O(n)시간이 필요하다.
더 좋은 방법은 2진 검색 알고리즘을 사용하는 것이다.
이곳의 직감은--**
패턴이 피봇 주위를 회전합니다.따라서 만약 우리가 축의 왼쪽에 있다면 값은 항상 축 오른쪽의 값보다 크다.그래서 우리는 오른쪽으로 가기로 결정할 수 있다.
마찬가지로 축의 오른쪽에 있으면 값이 축의 왼쪽보다 작거나 맨 오른쪽보다 작습니다.
**
만약 우리가 추축에 있다면 그것은 다음과 같은 조건을 만족시킬 것이다.arr[pivot-1] < arr[pivot] < arr[pivot + 1]따라서 상술한 직감을 이용하여 우리는 다음과 같은 해결 방안을 얻어냈다.

def findMin(self, nums: List[int]) -> int:
        arr = nums
        lo = 0
        hi = len(arr) - 1
        while lo <= hi:
            mid = (lo + hi) // 2
            if lo == hi:
                return arr[lo]
            if arr[0] < arr[mid] < arr[hi]:
                return arr[0]
            if arr[mid-1] > arr[mid] and arr[mid] < arr[mid+1]:
                return arr[mid]
            else:
                if arr[mid] > arr[hi] :
                    lo = mid + 1
                else:
                    hi = mid - 1