[리트코드] 153 - Find Minimum in Rotated Sorted Array(Java)

문제 설명

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

Suppose an array of length n sorted in ascending order is rotated between 1 and n times. For example, the array nums = [0,1,2,4,5,6,7] might become:

• [4,5,6,7,0,1,2] if it was rotated 4 times.
• [0,1,2,4,5,6,7] if it was rotated 7 times.

Notice that rotating an array [a[0], a[1], a[2], ..., a[n-1]] 1 time results in the array [a[n-1], a[0], a[1], a[2], ..., a[n-2]].

Given the sorted rotated array nums of unique elements, return the minimum element of this array.

You must write an algorithm that runs in O(log n) time.

---

🔍 접근법

이 문제의 핵심은 배열이 정렬된 상태에서 회전되었다는 점에 있다.

즉, 다음과 같은 특성이 있다:

• 회전되었으므로 배열은 두 개의 오름차순 정렬된 구간으로 나뉘게 된다.
• 최솟값은 항상 두 구간의 경계 지점에 위치한다.
• 배열의 끝 값(nums[end])은 중요한 기준점 역할을 한다.

이를 기반으로 이진 탐색을 적용할 수 있다.

---

💻 코드

class Solution {
    public int findMin(int[] nums) {
        int start = 0;
        int end = nums.length-1;
        int mid = 0;

        while(start < end){
             mid = start + (end - start)/2;
                
            if(nums[mid] < nums[end]){ //mid 지점이 현재 min의 왼쪽 영역에 위치
                end = mid;    
            }else{ //mid 지점이 현재 min의 오른쪽 영역에 위치
                start = mid + 1;
            }
        }
        return nums[start];
    }
}

nums[mid] < nums[end]일 경우 mid가 최솟값일 가능성이 있으므로 end = mid로 설정해 탐색 구간에 포함시키지만, nums[mid] > nums[end]일 경우 mid는 회전된 배열의 왼쪽 정렬 구간에 있어 최솟값이 될 수 없으므로 start = mid + 1로 설정해 탐색에서 제외합니다. 이는 이분 탐색의 종료 조건인 start == end를 만족시킬 때, 최솟값이 정확히 한 지점에 수렴하도록 보장하는 방식입니다.

---

💡 정리

• 이진 탐색의 종료 조건은 start == end, 즉 후보가 하나만 남을 때다.
• 탐색 범위를 줄일 때 mid가 최소값일 수 있는 경우에는 end = mid로 포함시키고, 최소값이 될 수 없는 경우는 start = mid + 1로 제외시켜 왔다.
• 이 과정을 반복하면서 start ~ end 범위에는 항상 최소값이 포함되어 있었고, 결국 단 하나의 값으로 수렴된다.
• 따라서 이 시점에서 nums[start] == nums[end]는 반드시 최소값이 되며, 두 값은 같기 때문에 아무 쪽을 리턴해도 된다.

---