Leetcode - 153. Find Minimum in Rotated Sorted Array

문제

오름차순 정렬된 배열이 몇차례 회전한 상태로 주어진다. 가령 [3,4,5,1,2]는 [1,2,3,4,5] 가 3번 회전한 상태. 이때 배열에서 가장 작은 수를 찾아서 리턴하라. 단 시간복잡도는 O(logn)이하 이어야한다.

Input: nums = [3,4,5,1,2]
Output: 1
Explanation: The original array was [1,2,3,4,5] rotated 3 times.

아이디어

아래 네가지 모든 경우의 수를 따져보면,
주어진 범위에서 nums[mid] < nums[right] 이라면 정답위치는 반드시 [left] ~ [mid] 사이에 있다.

[2,3,4,5,6,0,1]
       ^     ^
[6,0,1,2,3,4,5]  answer must be in left part
       ^  <  ^
[0,1,2,3,4,5,6]  answer must be in left part
       ^  <  ^
[1,2,3,4,5,6,0]
       ^     ^

바이너리 서치에서 좌우 범위를 좁히는 조건을 찾는게 생각보다 오래걸렸다. 이럴땐 모든 경우의 수를 적어보고 패턴을 찾아보는게 더 빠를것같다. 결과적으로 그 조건이 대단히 간단해서 놀랐음(?)

해결

class Solution {
public:
    int findMin(vector<int>& nums) {
        int left = 0, right = nums.size() - 1, mid = 0;
        while (left < right) {
            mid = left + (right - left) / 2;
            if (nums[mid] < nums[right])
                right = mid;
            else
                left = mid + 1;
        }
        return nums[left];
    }
};