[JS] Search in Rotated Sorted Array

🔒 문제 (LeetCode 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.

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

 

🌊 입출력

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

 

---

 

🔑 해결

🌌 알고리즘 - 이분탐색

배열을 mid 기준으로 나누었을 때 왼쪽과 오른쪽 중 적어도 한쪽은 항상 정렬된 상태가 된다. 정렬된 쪽에서 target을 탐색하였을 때 찾지 못한 경우 다른 쪽을 검사하기 위해 left 또는 right을 변경하여 범위를 바꾸고 재탐색한다.

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var search = function(nums, target) {
    let l = 0;
    let r = nums.length - 1;
    
    while(l <= r) {
        let mid = l + r >>> 1;
        
        if(nums[mid] === target) {
            return mid;
        }
        
        // 왼쪽이 정렬된 상태인 경우 target 찾기
        if(nums[l] <= nums[mid]) {
            if(nums[l] <= target && target <= nums[mid]) {
                r = mid - 1;	// target은 왼쪽에
            } else {
                l = mid + 1;	// target은 오른쪽에
            }
        } 
        
        // 오른쪽이 정렬된 상태인 경우 target 찾기
        else {
            if(nums[mid] <= target && target <= nums[r]) {
                l = mid + 1;	// target은 오른쪽에
            } else {
                r = mid - 1;	// target은 왼쪽에
            }
        }
    }
    
    return -1;
};