[LeetCode/Top Interview 150] [Binary Search] 153. Find Minimum in Rotated Sorted Array

문제 링크: https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/?envType=study-plan-v2&envId=top-interview-150
사용 언어: Java(OpenJDK 17. Java 8)

난이도: medium

문제:

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.

Example 1:

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

Input: nums = [4,5,6,7,0,1,2]
Output: 0
Explanation: The original array was [0,1,2,4,5,6,7] and it was rotated 4 times.
Example 3:

Input: nums = [11,13,15,17]
Output: 11
Explanation: The original array was [11,13,15,17] and it was rotated 4 times.

Constraints:

n == nums.length
1 <= n <= 5000
-5000 <= nums[i] <= 5000
All the integers of nums are unique.
nums is sorted and rotated between 1 and n times.

전략:

O(log n)만에 k회 (1<=k<=배열의 길이n) 회전한 오름차순 배열의 최소값을 찾아야 하는 문제.
배열의 모든 요소는 유니크한 값을 가진다.

이진탐색으로 마찬가지로 오름차순인 구역과 그렇지 않은 구역을 구분해 나가며 탐색한다.

코드 구현:

class Solution {
    public int findMin(int[] nums) {
        int lo=0, hi=nums.length-1;
        // 한바퀴 돌아서 원래대로 전체 배열이 오름차순인 경우 즉시 0번째 요소 리턴
        if (nums[lo]<=nums[hi]) { return nums[lo]; }

        while (lo < hi) {
            int m = (hi+lo)/2;
            // 현재 구간이 오름차순인 경우
            if (nums[lo]<=nums[m] && nums[m]<=nums[hi]) {
                return nums[lo];
            } else { // 오름차순이 아니라면
                // 왼쪽부터 중간까지는 오름차순이었던 경우
                // -> 우측 어딘가에서 최소값 시작
                if (nums[lo]<=nums[m]) {
                    lo=m+1;
                } else {
                    hi=m;
                }
            }
        }
        return nums[lo];
    }
}
Time: 0 ms (100%), Space: 40.38MB (97.69%) - LeetHub

실행결과:
https://github.com/1-vL/LeetCode/blob/main/0153-find-minimum-in-rotated-sorted-array/0153-find-minimum-in-rotated-sorted-array.java

Solutions 탭의 타인 코드:

public class Solution {
    public int findMin(int[] num) {
        if (num == null || num.length == 0) {
            return 0;
        }
        if (num.length == 1) {
            return num[0];
        }
        int start = 0, end = num.length - 1;
        while (start < end) {
            int mid = (start + end) / 2;
            if (mid > 0 && num[mid] < num[mid - 1]) {
                return num[mid];
            }
            if (num[start] <= num[mid] && num[mid] > num[end]) {
                start = mid + 1;
            } else {
                end = mid - 1;
            }
        }
        return num[start];
    }
}
Time: 0 ms (100%), Space: 40.9 MB (42.01%) - LeetHub

회고:

역시 연속으로 이진탐색 문제를 풀었더니 익숙해 진 것 같다. 직전에 풀었던 Search in Rotated Sorted Array와 유사하지만 체감상 훨씬 쉬운 느낌이었다.