[LeetCode] 153. Find Minimum in Rotated Sorted Array 풀이 (Java)

✔️ 오늘의 리트코드 공부 기록 – Find Minimum in Rotated Sorted Array

문제 요약 (Find Minimum in Rotated Sorted Array)

오름차순 정렬된 배열이 한 번 회전되었다.
이 배열에서 최소값을 O(logN) 시간에 구하라.

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

---

🤔 처음 떠올린 아이디어

처음에는 이렇게 생각했다.

그냥 전체를 한 번 순회하면서 최소값 찾으면 되지 않을까?

하지만 문제 조건은 O(logN).

즉, 이건 선형 탐색이 아니라
👉 Binary Search 문제라는 뜻이다.

그럼 이런 질문이 생긴다.

“회전됐는데 이진 탐색이 가능해?”

---

💡 핵심 깨달음: 회전 배열은 두 개의 정렬 구간이다

예시:

[4,5,6,7,0,1,2]

이 배열은 사실:

[4,5,6,7] + [0,1,2]

즉,
두 개의 오름차순 정렬 배열이 이어 붙은 형태다.

그리고 최소값은
👉 두 구간이 갈라지는 지점 (pivot)에 있다.

---

🧠 그럼 무엇을 판단해야 할까?

이진 탐색의 핵심 질문은 하나다.

mid가 어느 구간에 속하는가?

이를 위해
nums[mid]와 nums[right]를 비교한다.

---

경우 1️⃣

nums[mid] > nums[right]

→ mid는 “큰 값 구간”에 있다.
→ 최소값은 오른쪽에 있다.

left = mid + 1

---

경우 2️⃣

nums[mid] <= nums[right]

→ mid는 “작은 값 구간”에 있다.
→ 최소값은 왼쪽 (mid 포함)에 있다.

right = mid

---

좋아 😎
블로그용으로 자연스럽게 다시 써줄게.
(너 기존 톤 유지해서)

---

🔒 왜 right를 기준으로 비교할까?

이 부분이 처음엔 가장 헷갈렸다.

왜 left가 아니라 right와 비교할까?

핵심은 이 한 문장이다.

우리는 항상 “최소값이 [left, right] 안에 있다”는 상태를 유지한다.

이 상태에서 right는
항상 현재 탐색 구간의 끝 값이다.

---

그럼 left는 왜 안 될까?

탐색이 진행되면서 이런 일이 생긴다.

처음에는 left가 큰 값 구간에 있다.
하지만 탐색 범위를 줄이다 보면
어느 순간 left도 작은 값 구간에 들어가게 된다.

즉,

• 어떤 때는 큰 구간
• 어떤 때는 작은 구간

👉 left는 어느 구간에 속하는지 보장되지 않는다.

그래서 기준점으로 쓰기에는 불안정하다.

---

🔁 왜 right = mid 인가?

mid가 최소값일 가능성이 있기 때문이다.

만약 right = mid - 1을 하면
정답을 건너뛸 수 있다.

---

코드 (Java)

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

        while (left < right) {
            int mid = left + (right - left) / 2;

            if (nums[mid] > nums[right]) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }

        return nums[left];
    }
}

---

📈 시간 / 공간 복잡도

시간: 매번 탐색 범위를 절반으로 줄임 → O(logN)
공간: 변수 몇 개만 사용 → O(1)

---

📝 이번 문제에서 얻은 깨달음

• 회전 배열은 “완전히 깨진 배열”이 아니다.
• 정렬은 한 번만 깨진다.
• 이진 탐색은 정렬이 유지되는 구간을 버리는 과정이다.
• 비교 기준점을 어떻게 잡느냐가 문제의 핵심이다.

---

👉 결국 중요한 건

“이 배열은 단 한 번만 정렬이 깨졌다”는 사실을 이용하는 것.

그리고

불변식: 최소값은 항상 [left, right] 안에 있다.

Binary Search는
값을 찾는 기술이 아니라
구간을 줄이는 기술이라는 걸 다시 느꼈다.

---