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

조건만 좀 복잡해졌지 그 조건을 떠올리기만 하면 기본 이진탐색으로 풀기 가능

 

1. 접근 방법

(1) mid기준 오른쪽이 정렬됐을 경우와, mid기준 왼쪽이 정렬됐을 경우를 나눈다.

        if (nums[left] <= nums[mid]) { 
        // ...
        } else {
        // ...
        }

 

(2) 각 조건에서, 정렬된 쪽에 target이 있는 경우와, 정렬된 쪽에 target이 없는 경우를 나눈다. 

        if (nums[left] <= nums[mid]) {
            if (nums[left] <= target && target <= nums[mid]) {
            // ...
            } else {
            // ...
            }
        } else {
            if (nums[mid] <= target && target <= nums[right]) {
            // ...
            } else {
            // ...
            }
        }

그냥 left와 mid 사이에 target이 있는지 또는 mid와 right 사이에 target이 있는지 확인하면 된다.

 

(3) 각 조건 안에서 left 또는 right의 위치를 바꿔준다. 그냥 기본 이진탐색스럽게 옮겨 주면 된다.

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

 

2. 전체 풀이

var search = function(nums, target) {
    let left = 0;
    let right = nums.length - 1;
    let mid = 0;
    
    while (left <= right) {
        mid = Math.floor((left + right) / 2);
        
        if (nums[mid] === target) return mid;
        if (nums[left] <= nums[mid]) {
            if (nums[left] <= target && target <= nums[mid]) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        } else {
            if (nums[mid] <= target && target <= nums[right]) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
    }
        
    return -1;
};

나이스샷 -👍🏻

코테가 이정도로만 나오면 좋겠넴