[LeetCode] 153. Find Minimum in Rotated Sorted Array (C++)

문제

 

https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/

Find Minimum in Rotated Sorted Array - LeetCode

 

풀이

 

난이도: Medium 

 

 

정렬되었지만 회전된(?) 배열에서 최솟값을 찾는 문제. 정렬된 원형 힙을 생각하면 편할 것 같다.

물론 단순하게는 배열을 순서대로 탐색하는 것으로 O(n)의 알고리즘을 만들 수 있지만,

O(log n)의 시간 복잡도를 가지는 알고리즘을 만들어야 한다.

 

O(log n)이면 생각나는게 바로 이분탐색인데, 이번 문제도 이분 탐색으로 해결 가능하다.

 

회전 전

 

 

회전 후

배열이 회전한다면, 최소값은 정렬된 배열의 마지막 값(최댓값)의 다음 값으로 존재할 것이다.

만약 현재 범위의 가장 왼쪽(left)값과 가장 오른쪽(right) 값을 비교하였을 때 left의 값이 더 크다면 현재의 [left,right]

의 범위 내에 시작(최솟값) 점이 있다는 것이다.

 

이제 범위를 점점 좁혀가면서 시작점을 찾으면 되는데, 이분 탐색은 기본적으로 left와 right의 중간값을 mid로 설정하여 [left, mid]와 [mid+1, right]의 두 범위로 나눈다.

 

이번에는 [left, mid]와 [mid+1, right] 두 범위 중에 어떤 부분이 시작점을 포함하고 있을지 생각해보자.

시작점을 포함하는 범위는 위와 같이 범위의 양 끝이 값이 역순(left>right)일 것이고,

포함하지 않는 범위는 정상적으로 정렬된 부분 배열이므로 오른쪽 끝 값이 더 클 것이다.(left<right)

따라서 분할의 기준이 되는 mid값보다 left값이 크다면 [left, mid]범위로,

반대라면 [mid+1, right]로 탐색을 줄여나가는 것이 이분 탐색의 핵심이 된다.

 

 

코드