숫자로 주워진 배열에서 타겟값의 인덱스를 찾는 문제. O(logn) (배열이 정렬된 상태에서 회전되어있음)
O(logn) 으로 풀기위해서
이진탐색
을 이용함.
/**
* @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)
}
};