문제

n개의 요소를 가진 정렬된 배열이 존재한다.
배열이 1 ~ n번 회전된 상태로 주어졌을때 배열의 최소 요소를 반환해야한다.
O(log n) 시간복잡도를 가져야한다.

Input: nums = [3,4,5,1,2]
Output: 1
Explanation: The original array was [1,2,3,4,5] rotated 3 times.

구현 전 예상 풀이

선형적으로 배열을 탐색하면 O(n) 시간 복잡도를 가지므로 다른 방법으로 풀어야한다.

배열을 절반으로 나누어서 왼쪽에서 가장 작은값과 오른쪽에서 가장 작은 값을 찾아서 비교하는 로직을 재귀적으로 구현하면 O(log n)시간복잡도를 가질 것이다.

구현 코드

class Solution {
    int[] nums;
    public int findMin(int[] nums) {
        this.nums = nums;
        return find(0, nums.length - 1);
    }

    private int find(int start, int end) {
        if (start == end) {
            return nums[start];
        }
        int mid = (start + end) / 2;
        int left = find(start, mid);
        int right = find(mid + 1, end);
        return Math.min(left, right);
    }
}

개선점

내가 생각한 풀이는 병합정렬이다

이진 탐색은 정렬 되어있다고 가정하고, 중앙값이 타겟보다 작으면 오른쪽으로, 크면 왼쪽으로 탐색한다.
이 문제는 따로 타겟이 없고, 로테이션된 정렬된 배열에서 가장 작은 값을 찾는 것 이므로 중앙값이 배열 마지막 값보다 크면 오른쪽, 작으면 왼쪽으로 탐색한다.

class Solution {
    public int findMin(int[] nums) {
        int start = 0;
        int end = nums.length - 1;
        while (start < end) {
            int mid = (start + end) / 2;
            if (nums[mid] > nums[end]) {
                start = mid + 1;
            } else {
                end = mid;
            }
        }

        return nums[start];
    }
}

153. Find Minimum in Rotated Sorted Array
참고한 풀이 링크