[LeetCode] Find Minimum in Rotated Sorted Array - 자바스크립트 풀이

문제 링크

이전 회전배열 탐색 문제 풀고 오니 핵쉬움 3분컷(문제 풀이 조건이 쉽게 주어지긴 했음)

 

1. 접근 방법

(1) mid 값이 mid - 1 값보다 작은 경우, 회전된 상태에서 mid값이 인덱스 0인 경우이므로 mid의 값을 반환한다.

        if (nums[mid - 1] > nums[mid]) return nums[mid];

 

(2) mid 기준 왼쪽이 정렬된 상태면 left를 mid + 1로 옮겨 준다,

(3) mid 기준 오른쪽이 정렬된 상태면 right를 mid로 옮겨 준다.

        if (nums[0] < nums[mid]) {
        // 왼쪽이 정렬된 상태일 때
            left = mid + 1;
        } else {
        // 오른쪽이 정렬된 상태일 때
            right = mid;
        }

 

(4) 주어지는 배열의 길이가 1이거나 또는 처음부터 회전 안한 상태의 정렬된 배열이 인자로 넘어오는 경우 예외처리로 인덱스 0 값을 반환한다.

    if (nums.length === 1 || nums[0] < nums[nums.length - 1]) return nums[0];

 

2. 전체 풀이

/**
 * @param {number[]} nums
 * @return {number}
 */
var findMin = function(nums) {
    if (nums.length === 1 || nums[0] < nums[nums.length - 1]) return nums[0];
    
    let left = 0;
    let right = nums.length;
    let mid = 0;
    
    while (left < right) {
        mid = left + Math.floor((right - left) / 2);
        if (nums[mid - 1] > nums[mid]) return nums[mid];
        
        if (nums[0] < nums[mid]) {
        // 왼쪽이 정렬된 상태일 때
            left = mid + 1;
        } else {
        // 오른쪽이 정렬된 상태일 때
            right = mid;
        }
    }
    
    return nums[left];
};