[PS] Leet | 33. 정렬된 회전 배열에서의 탐색

문제

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

Prior to being passed to your function, nums is possibly rotated at an unknown pivot 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 rotated at pivot index 3 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

조건

• 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

답

이진 탐색을 사용합니다.

 

단, 회전하는 정렬된 배열이기 때문에, 중앙을 기준으로 최댓값/최솟값 전환 지점이 어디에 있는지(오른쪽 또는 왼쪽) 구분 후 탐색을 진행해 주어야 합니다.

 

전환지점이 오른쪽에 있다면, 왼쪽 구간이 단조 증가가 보장됩니다.

 

전환지점이 왼쪽에 있다면, 오른쪽 구간이 단조 증가가 보장됩니다.

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

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

        if (nums[mid] < nums[right]) {
            if (nums[mid] < target && target <= nums[right]) {
                left = mid + 1;
            } else {
                right = mid;
            }
        } else {
            if (nums[left] <= target && target <= nums[mid]) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
    }

    return (nums[left] === target)? left : -1;
};