LeetCode Search in Rotated Sorted Array (JavaScript)

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

문제 설명

There is an integer array nums sorted in ascending order (with distinct values).

Prior to being passed to your function, nums is possibly left rotated at an unknown index k (1 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (0-indexed). For example, [0,1,2,4,5,6,7] might be left rotated by 3 indices and become [4,5,6,7,0,1,2].

Given the array nums after the possible rotation and an integer target, return the index of target if it is in nums, or -1 if it is not in nums.

You must write an algorithm with O(log n) runtime complexity.

Example 1:

Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4

Example 2:

Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1

Example 3:

Input: nums = [1], target = 0
Output: -1

Constraints:

• 1 <= nums.length <= 5000
• 104 <= nums[i] <= 104
• All values of nums are unique.
• nums is an ascending array that is possibly rotated.
• 104 <= target <= 104

---

문제 풀이

mid를 기준으로 왼쪽, 오른쪽 둘 중 하나는 정렬이 되어있다를 이용하여 문제를 접근

1. mid를 기준으로 좌측이 정렬되어 있는 경우 (nums[left] <= nums[mid])

• target이 좌측안에 존재하는지 판단
  • 있다면 right 값을 mid - 1로
  • 없다면 우측에 있으므로 left 값을 mid + 1로

2. mid를 기준으로 우측이 정렬되어 있는 경우 (nums[mid] <= nums[right])

• target이 우측안에 존재하는지 판단
  • 있다면 left 값을 mid + 1로
  • 없다면 좌측에 있으므로 right 값을 mid - 1로

3. mid 값이 target과 같다면 mid 리턴

4. while 문이 끝나면 발견을 하지 못하는 값이므로 -1 리턴

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var search = function(nums, target) {
    let [left, right] = [0, nums.length - 1];

    while (left <= right) {
        const mid = Math.floor((left + right) / 2);

        if (nums[mid] === target) {
            return mid;
        }

        // mid 기준 좌측이 정렬되어있다.
        if (nums[left] <= nums[mid]) {
            // 좌측 정렬 안에 값이 존재하는지 확인
            if (nums[left] <= target && target < nums[mid]) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        } else { // mid 기준 우측이 정렬되어있다.
            // 우측 정렬 안에 값이 존재하는지 확인
            if (nums[mid] < target && target <= nums[right]) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
    }

    return -1;
};

---

결론

Binary Search를 어떻게 진행할 건지를 판단하는게 핵심

보통은 모두 정렬된 상태에서 Binary Search를 진행하지만 이 문제는 정렬이 되어있지 않음.

따라서 정렬된 구간을 통해 값을 구해나가는 방식으로 문제를 접근해야 함.