LeetCode Find Minimum in Rotated Sorted Array (JavaScript), Binary Search

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

문제 설명

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.

---

문제 풀이

접근 방식

1. 정렬되지 않은 배열에서 최소 값을 구하기위해 Binary Search를 이용 (O(log n)으로 해결해야 하므로 일반적인 알고리즘은 시간 초과)
2. 현재 mid값을 기준으로 left, right를 어떻게 움직일 것인가?
   • mid 값보다 right값이 더 작다면 -> 더 작은 숫자가 우측에 있음 -> left 값을 mid + 1로 변경
   • mid 값 < right 값 이라면 -> 좌측에 존재 -> right 값을 mid - 1로 변경

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

    let [left, right] = [0, nums.length - 1];

    while (left <= right) {
        const mid = Math.floor((left + right) / 2);
        answer = Math.min(answer, nums[mid]);

        if (nums[mid] > nums[right]) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    return answer;
};

---

결론

left, right 값을 조정하기위해 어떤 값(mid)을 기준으로 할 것인지 판단하고,

그 값을 기준으로 left, right를 어떻게 이동할 건지를 생각해야 하는 문제