문제

https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/description/?envType=study-plan-v2&envId=top-interview-150

해결 방법

• 33. Search in Rotated Sorted Array의 해결방법과 매우 유사
• 이 문제도 O(log n)의 시간 복잡도로 해결해야 하기 때문에 전체를 순회할 수 없고, 이분탐색으로 순회해야 함
• [0, 1, 2, 4, 5, 6, 7]을 4번 회전한 [4, 5, 6, 7, 0, 1, 2]에서 최소값을 찾는다고 가정했을 때, 발생할 수 있는 구간을 생각해보면
  1. [4, 5, 6, 7], [0, 1, 2]와 같이 정렬된 구간이 주어진 경우 => 맨 처음 값과 현재 min 값 중 작은 값을 min으로 갱신 + 더 이상 이분탐색을 진행할 필요 없음
  2. [6, 7, 0, 1, 2]와 같이 정렬된 구간이 섞여있는 경우 => mid 값만 min값과 비교해주고 구간을 다시 2개로 나눠 이분탐색 진행

코드

class Solution {
    private static int min;

    public int findMin(int[] nums) {
        min = Integer.MAX_VALUE;
        binarySearch(nums, 0, nums.length - 1);
        return min;
    }

    private static void binarySearch(int[] nums, int left, int right) {
        if (left > right) return;
        if (nums[left] < nums[right]) {
            min = Math.min(min, nums[left]);
            return;
        }

        int mid = (left + right) / 2;
        min = Math.min(min, nums[mid]);
        binarySearch(nums, left, mid - 1);
        binarySearch(nums, mid + 1, right);
    }
}

결과