이것은 이진 검색의 변형입니다.
오름차순으로 정렬되면 키워드를 볼 수 있습니다. log n의 시간 복잡도
그러나 회전을 해서 일반적인 이진탐색 문제가 아니며 특정 값이 아닌 임의의 최소값을 찾는 문제임을 알 수 있다.
아래는 기본 이진 검색 알고리즘입니다.
def binary_search(arr, target):
left = 0
right = len(arr) - 1
while left <= right:
mid = (left + right) // 2
if arr(mid) == target:
return mid
if arr(mid) < target:
left = mid + 1
else:
right = mid - 1
return -1
l 포인터와 r 포인터를 각각 배치하여 중간 인덱스의 값과 크기를 비교하여 포인터를 오른쪽 범위 또는 왼쪽 범위로 조정하여 검색 범위를 조정합니다.
O(로그 n)
이진 검색 알고리즘 응용 솔루션
class Solution:
def findMin(self, nums: List(int)) -> int:
#최소값을 구하라. 제약조건 log n
#최소값이 리스트 맨 뒤에 있다면?
res = nums(0)
l, r =0, len(nums) - 1
while l <= r:
if nums(l) < nums(r):
res = min(res, nums(l))
break
m = (l+r) // 2
res = min(res, nums(m))
if nums(m) >= nums(l):
l = m + 1
else:
r = m - 1
return res
먼저 l과 r을 포인터로 선언합니다.
res는 이미 정렬된 최상의 경우를 가상 목록의 첫 번째 인덱스 값으로 초기화합니다.
오른쪽 끝 위치 값이 왼쪽 끝 위치로 이동하면 회전이 발생합니다. 즉, 회전 횟수가 n * x 번만 발생하지 않은 경우 왼쪽 값이 항상 오른쪽 값보다 큽니다.
그러면 왼쪽 포인터가 오른쪽 포인터보다 작거나 같은 조건으로 while 문이 실행된다.
먼저 포인터 l과 포인터 r의 인덱스에 해당하는 값을 비교합니다(이미 정렬된 최상의 시나리오).
(단지 초기 상황을 말하는 것이 아닙니다. 검색 범위를 좁혀도 좁혀진 범위는 이미 정렬되어 있을 수 있습니다.
예(4,5,6,7,0,1,2)
이미 비교로 정렬되어 있으면 res와 왼쪽 포인터의 값을 비교하여 작은 값을 결과 값으로 업데이트하고 중단합니다.
그런 다음 중간 포인터를 업데이트합니다.
m = (l + r) // 2
중앙값과 res 값을 비교하고 최소값을 res에 넣습니다.
그 후 포인터가 어떻게 좁혀질지 4분의 1입니다.
가운데 포인터에 해당하는 값이 왼쪽 포인터에 해당하는 값보다 크거나 같으면 오른쪽 범위를 찾습니다.
아시다시피 회전은 오른쪽 끝 위치 값이 왼쪽 끝 위치로 이동할 때 발생합니다. 중앙값이 가장 왼쪽 값보다 크거나 같으면 이미 순회가 발생하여 최소값이 오른쪽에 있습니다. (4,5,6,7,0,1,2) 것입니다.)
중앙값이 가장 왼쪽 값(7,0,1,2,3,4,5,6,)보다 작으면 최소값이 왼쪽에 있습니다.