[토이14]
rotatedArraySearch
문제
부분적으로 오름차순 정렬*된 정수의 배열(rotated)과 정수(target)를 입력받아 target의 인덱스를 리턴해야 합니다.
입력
인자 1 : rotated
number 타입을 요소로 갖는 배열
rotated[i]는 정수
인자 2 : target
number 타입의 정수
출력
number 타입을 리턴해야 합니다.
주의사항
rotated에 중복된 요소는 없습니다.
target이 없는 경우, -1을 리턴해야 합니다.
const rotatedArraySearch = function (rotated, target) {
for (let i = 0; i < rotated.length; i++) {
if (rotated[i] === target) {
return i
}
}
}
// 뭔가 시도해보는듯하다가..이진탐색으로.. 어떻게해야할지..
// binary search를 다시 공부해야할것같다... 휴 하핳
// naive solution
const rotatedArraySearch = (rotated, target) => {
for (let i = 0; i < rotated.length; i++) {
if (rotated[i] === target) {
return i;
}
}
return -1;
};
----------------------------------------------------------
const rotatedArraySearch = function (rotated, target) {
let left = 0,
right = rotated.length - 1;
while (left <= right) {
let middle = parseInt((right + left) / 2);
if (rotated[middle] === target) {
return middle;
}
if (rotated[left] < rotated[middle]) {
// 왼쪽 절반이 정렬되어 있는 상태
if (target < rotated[middle] && rotated[left] <= target) {
right = middle - 1;
} else {
left = middle + 1;
}
} else {
// 오른쪽 절반이 정렬되어 있는 상태
if (target <= rotated[right] && rotated[middle] < target) {
left = middle + 1;
} else {
right = middle - 1;
}
}
}
return -1;
};