[Java] 153. Find Minimum in Rotated Sorted Array

문제 파악

rotated 된 배열 nums의 최솟값을 찾는 문제이다.

 

시간 복잡도는 O(logN) 을 만족해야한다.

 

---

풀이

1️⃣ 이분 탐색을 이용한 풀이

💡 떠오른 Idea

이전에 풀었던 Search in Rotated Sorted Array 문제의 일부분과 같은 문제라서 쉽게 해결할 수 있었다.

이분 탐색을 진행하는데, mid 위치의 값과 right 위치의 값을 비교해서 mid 값이 작은 경우,

mid 위치의 원소들은 오름차순으로 구성되어 있음을 보장할 수 있기 때문에 탐색 영역을 왼쪽 영역으로 이동하는 방식으로 구현하면 된다.

 

class Solution {
    public int findMin(int[] nums) {
        int left = 0, right = nums.length - 1;
        while (left < right) {
            int mid = (left + right) / 2;
            System.out.println(mid);
            if (nums[mid] < nums[right]) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return nums[left];
    }
}

 

결과

 

---

📖 회고

이번 주차 문제들은 이분 탐색을 단순히 특정 원소를 찾는데에 사용한 것이 아니라

 

응용해서 활용해야하는 문제들이 많았다.

 

비슷한 유형들을 풀어보니 어떤식으로 조건을 생각해야하는지 감이 온 것 같다.