[LeetCode] Find Minimum in Rotated Sorted Array - 21.08.31

📄 문제

배열에서 최솟값을 찾는 문제. 단, 오름차순으로 정렬된 배열이 랜덤 횟수로 rotate ([1, 2, 3, 4, 5] -> [2, 3, 4, 5, 1]) 되어 있다는 조건이 존재한다. 그리고 코드는 O(log n)의 시간복잡도로 짜야한다.
문제 링크

🔍 코드

class Solution {
    public int findMin(int[] nums) {
        int left = 0;
        int right = nums.length - 1;
        if (nums.length == 1) {
            return nums[0];
        }
        
        if (nums[left] < nums[right]) {
            return nums[left];
        }

        while(true) {
            int mid = (left + right) / 2;
            if (nums[left] < nums[mid]) {
                left = mid;
            } else if (nums[left] > nums[mid]) {
                right = mid;
            } else {
                break;
            }
        }
        return nums[left + 1];
    }
}

✅ 풀이

O(log N) 시간 복잡도면 binary search가 가장 먼저 떠올라서 적용하였더니 풀렸다. binary search를 억지로 적용시키려 하면 풀리지 않고, if (nums[left] < nums[right]) 이 부분을 먼저 처리한 다음 구현하여야 한다.