[LeetCode] 153. Find Minimum in Rotated Sorted Array - 이진탐색(Binary Search) JAVA

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

코드설명

이진탐색(Binary Search) 을 활용합니다.

 

문제에서 무엇을 구하라는 것인가? 하는 의문이 듭니다.

이유는, 가장 작은 최소값을 구하라고 하며, 문제에서 계속 설명하는 것은 주어진 배열은 [1 .. a[n-1]] 의 숫자로 이루어진 배열이 rotate된 값이라는 것 이기 때문입니다.

 

왜 이 부분을 이야기했을까요?

이유는, 이진탐색을 사용하려면 "정렬된" 상태에서만 사용할 수 있기 때문입니다.

 

이러한 점을 이용하여, num[md]가 마지막 값 num[end]보다 크다면, 가장 작은 값은 mid ~ end 사이에 있음을 알 수 있고, left = mid로 옮겨 그 [mid ~ end] 안에서 탐색하면 되겠습니다.

코드

정답코드1입니다.

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

    public int binarySearchMin(int start, int end, int[] nums) {
        int left = start - 1;
        int right = end + 1;

        while (left + 1 < right) {
            int mid = (left + right) / 2;
            
            // nums[mid]가 마지막 값(nums[end])보다 크다면, 최소값은 오른쪽에 있음
            if (nums[mid] > nums[end]) {
                left = mid;
            } else {
                right = mid;
            }
        }
        return nums[right]; // right가 최솟값 위치
    }
}

 

처음에는 숫자를 정렬한뒤, binarySearch로 최소값을 찾으면 0의 위치를 찾을 수 있을 것 이라 생각했습니다.

실제로 정렬한뒤 이진탐색을 활용하면 가장 작은 원소값을 구할 수 있습니다.

하지만, 정렬의 시간복잡도는 O(n log n) 입니다.

class Solution {
    public int findMin(int[] nums) {
        
        System.out.println(binarySearchLowerBound(0, nums.length, -5000, nums));
//        Arrays.sort(nums);
        return binarySearchLowerBound(0, nums.length, -5000, nums);
    }

    public int binarySearchLowerBound(int start, int end, int target, int[] nums){
        int left = start - 1;
        int right = end + 1;

        while(left + 1 < right){
            int mid = (left + right) / 2;
            if(target <= nums[mid]){
                right = mid;
            }else if(target > nums[mid]){
                left = mid;
            }
        }
        return nums[right];
    }
}