[leetcode][154] Find Minimum in Rotated Sorted Array II

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

---

오름차순 정렬된 배열이 있을 때, 어떤 pivot으로 배열이 회전했다고 하자.

ex) [0,1,2,3,4,5,6,7] -> [4,5,6,7,0,1,2,3]

회전된 배열이 주어질 때 가장 작은 수를 구하라. 배열안에 수는 중복될 수 있다.

---

33번 Search in Rotated Sorted Array 와 비슷하게 풀었다.

위 문제와 다른 점은 33번 문제는 회전된 배열에서 특정 수 target을 찾고 배열은 중복된 수가 없다.

 

왼쪽	오른쪽	배열
오름차순	오름차순	오름차순 (제일 작은수가 왼쪽에 위치)
오름차순	내림차순	제일 작은수가 오른쪽에 위치
내림차순	오름차순	제일 작은수가 왼쪽에 위치
내림차순	내림차순	내림차순 (제일 작은수가 오른쪽에 위치)

그래서 기본적으로는 위 표를 보고 작은수가 있는 곳으로 탐색범위를 줄여가면서 가장 작은수를 찾아나갈 수 있다. (binary search).

그러나 오름차순인지 내림차순인지 확인을 위한 nums[처음], nums[중간], nums[마지막] 값들을 비교할 때 이들 중 같은 수가 나온다면 위와 같은 방법으로는 확인할 수 없다. ex) 1, 1, 1, 0, 1

따라서 nums[처음] = nums[중간] 이거나 nums[중간] = nums[마지막] 인 경우 분할정복으로 배열을 반 나누고 두 배열을 모두 탐색해나간다.

 

시간복잡도는 O(NlogN).

---

소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/hard/154.%20Find%20Minimum%20in%20Rotated%20Sorted%20Array%20II.cpp

---

여담이지만 분할정복이나 이진탐색 중 하나만 써도 제한시간 내에 풀 수 있다.