[Leet Code Top 100] #153. Find Minimum in Rotated Sorted Array

문제 정보

• Leet Code 문제 링크
• 난이도 : Medium

 

해결 방법

아래와 같이 O(log n) 시간 내에 해결하라는 문제가 아니었다면 return Math.min(...nums); // O(n) 와 같이 한줄에 풀 수도 있지만 log n 이라는 시간 복잡도 자체에 Binary Search 등의 알고리즘으로 풀어야 한다는 힌트가 있습니다.

You must write an algorithm that runs in O(log n) time.

left 와 right 를 설정하여 위의 (잘 알아보기가 힘든) 그림과 같이 nums[mid] 가 nums[left] 보다 큰 경우는 mid 가 오른쪽으로 이동해야 하므로 left 값에 기존 mid + 1 값을 넣습니다. 

첫 번째 구현에서는 예외 CASE 를 많이 생각하느라 rotate 되지 않은 Array 의 경우나 mid + 1 이나 mid -1 인 경우도 고려를 해서 종료 조건이 3가지로 나뉘었는데 Binary Search 는 index 나 mid 값만 잘 고려하면 훨씬 간단하게 구현되니 생각을 많이 해봐야 할 것 같습니다.

Discuss 탭에서 다른 풀이 몇 가지를 보다보니 알게 되었는데 Math.floor 대신 ~~ 를 사용할 수 있는데 가독성은 떨어지지만 성능은 더 좋다고합니다.

 

소스 코드

// Leet Code
// #153. Find Minimum in Rotated Sorted Array
// Success
// Runtime: 72 ms, faster than 80.11% of JavaScript online submissions for Find Minimum in Rotated Sorted Array.
// Memory Usage: 39.2 MB, less than 34.14% of JavaScript online submissions for Find Minimum in Rotated Sorted Array.

function main(){
    // Input // Output
    nums = [3,4,5,1,2]; // 1
    //nums = [1,2,3,4,5]; // 1
    //nums = [2,2,2,2,2]; // 2
    console.log(findMin(nums));
}

/**
 * @param {number[]} nums
 * @return {number}
 */
// var findMin = function(nums) {

//     if(nums[0] < nums[nums.length - 1]){
//        return nums[0]
//     }

//     const binarySearch = function(left, right){
//         let mid = Math.floor((left + right) / 2);

//         if(nums[mid + 1] < nums[mid]){
//             return nums[mid + 1];
//         }

//         if(nums[mid] < nums[mid - 1]){
//             return nums[mid];
//         }
        
//         if(left === right){
//             return nums[left];
//         }
        
//         if(nums[0] <= nums[mid]){
//             left = mid + 1;
//         } else {
//             right = mid - 1;
//         }

//         return binarySearch(left, right);
//     }
    
//     return binarySearch(0, nums.length - 1);    
// };

var findMin = function(nums) {
    //return Math.min(...nums); // O(n)

    const binarySearch = function(left, right){
        //console.log(`left:${left} / right:${right}`);
        
        // exit condition
        if(right <= left){
            return nums[left];
        }
        
        // set new left or right index
        const mid = Math.floor((left + right) / 2);
        if(nums[right] < nums[mid]){
            left = mid + 1;
        } else {
            right = mid;
        }

        // call recursive
        return binarySearch(left, right);
    }

    return binarySearch(0, nums.length - 1);    
};

main();

 

참고 자료

• LeetCode Top 100 Problem Selection
• LeetCode - Clean JavaScript solution
• MDN - Bitwise NOT (~)
• [JS] tilde(~)과 double tilde(~~)연산자