[LeetCode] 153. Find Minimum in Rotated Sorted Array (JS)

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

Find Minimum in Rotated Sorted Array - LeetCode

핵심 아이디어

• 문제 조건이 O(logN)으로 찾으라고 되어 있으니 binary search를 사용한다
  
  • 정렬된 array를 rotate해서 binary search를 응용할 수 있다
• 정렬이 안 맞기 시작하는 지점이 최솟값이니 정렬이 맞는 절반은 탐색에서 제외한다

 

복잡도

• 시간 복잡도: O(logN)
  
  • 탐색 범위를 1회당 반씩 좁히는 binary search
• 공간 복잡도: O(1)
  
  • 변수 4개

 

설명

정렬된 배열을 n회 rotate(오른쪽으로 밀어낸) 배열에서 최솟값을 logN 시간에 찾아야 하는 문제이다. 정렬된 배열이라면 left < mid < right가 성립할텐데, 회전한 배열이라면 어느 지점에서는 순서가 맞지 않을 것이고, 그 지점에 min이 있다.

 

코드 (Javascript)

/**
 * @param {number[]} nums
 * @return {number}
 */
var findMin = function(nums) {
    let result = nums[0];
    let leftIdx = 0;
    let rightIdx = nums.length - 1;
    let midIdx = Math.floor(nums.length);
    
    while (leftIdx <= rightIdx) {
        if(nums[leftIdx] < nums[rightIdx]) {
            result = Math.min(result, nums[leftIdx]);
            break;
        }
        
        midIdx = Math.floor((leftIdx + rightIdx) / 2);

        result = Math.min(result, nums[midIdx]);
        if(nums[leftIdx] <= nums[midIdx]) {
            leftIdx = midIdx + 1;
        } else {
            rightIdx = midIdx - 1;
        }
    }
    
    return result;
};

 

유튜브 NeetCode 해설 영상

 

여담

midIdx = Math.floor((leftIdx + rightIdx) / 2); 에서 (leftIdx + rightIdx) 괄호 빼먹고 왜 안 되지 하고 있었다... ㅎㅎ

PS에서도 안 될 땐 디버깅을 철저히 해야겠다