[Leetcode] 33. Search in Rotated Sorted Array

Problem

문제 링크

숫자로 주워진 배열에서 타겟값의 인덱스를 찾는 문제. O(logn) (배열이 정렬된 상태에서 회전되어있음)

Solution

O(logn) 으로 풀기위해서 이진탐색을 이용함.

1. 회전의 유무를 파악하고 있다면 회전하는 인덱스를 찾아낸다.
2. 회전하는 인덱스를 찾다가 타겟값이 운좋게 나오면 바로 해당 값을 리턴
3. 회전하는 인덱스를 찾는 방법
   • mid의 값이 left의 값보다 크다면 오름차순인 정상적인 배열이고, 아니라면 그 부분은 회전이 일어난 부분이다. 이 조건을 이용해서 회전하는 부분의 영역을 좁혀간다.
4. 회전하는 부분이 있을때, 타겟이 어느 범위에 있는지 확인하고 해당하는 범위안에서 이진탐색을통해 타겟값을 찾아낸다.

JS Code

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var search = function(nums, target) {
    function bsPosition () {
        let left = 0, right = nums.length
        
        while(left < right) {
            const mid = Math.floor((left + right) / 2)
            
            if (nums[mid] === target) return mid // 회전을 찾기전에 운좋게 타겟을 발견할 경우
            
            if (nums[left] < nums[mid]) left = mid
            else right = mid
        }
        
        return left + 1
    }
    
    const rotatedIdx = bsPosition()
    const isRotated = () => rotatedIdx !== nums.length
    
    function bsFindTarget (pLeft, pRight) {
        let left = pLeft, right = pRight
        
        while(left < right) {
            const mid = Math.floor((left + right) / 2)
            if (nums[mid] < target) left = mid + 1
            else right = mid
        }
        
        return target === nums[left] ? left : -1
    }
    
    if (isRotated()) {
        return nums[0] <= target ? bsFindTarget(0, rotatedIdx) : bsFindTarget(rotatedIdx, nums.length)
    } else {
        return bsFindTarget(0,nums.length)
    }
};