Toy_ #14. rotatedArraySearch
- 문제
부분적으로 오름차순 정렬
된 정수의 배열(rotated)과 정수(target)를 입력받아 target의 인덱스를 리턴해야 합니다.
부분적으로 정렬된 배열
: 배열을 왼쪽 혹은 오른쪽으로 0칸 이상 순환 이동할 경우 완전히 정렬되는 배열- 예시: [4, 5, 6, 0, 1, 2, 3]은 왼쪽으로 3칸 또는 오른쪽으로 4칸 순환 이동할 경우 완전히 정렬됩니다.
입출력 예시
let output = rotatedArraySearch([4, 5, 6, 0, 1, 2, 3], 2);
console.log(output); // --> 5
output = rotatedArraySearch([4, 5, 6, 0, 1, 2, 3], 100);
console.log(output); // --> -1
주의
- rotated에 중복된 요소는 없습니다.
- target이 없는 경우, -1을 리턴해야 합니다.
- 단순히 처음부터 끝까지 찾아보는 방법(O(N)) 대신 다른 방법(O(logN))을 탐구해 보세요.
- 풀이
인자로 받은 배열의 가운데 인덱스를 구하고 왼쪽과 오른쪽으로 나누어 target를 찾으려고 했다. 왼쪽, 오른쪽 배열로 나누어 재귀로 식을 썼지만 실패했다.
Reference code
const rotatedArraySearch = function (rotated, target) {
let left = 0, right = rotated.length - 1;
while (left <= right) {
const middle = parseInt((left + right) / 2);
if (rotated[middle] === target) {
return middle;
}
if (rotated[left] < rotated[middle]) {
// 절반 왼쪽이 정렬된 경우;
if (rotated[left] <= target && rotated[middle] > target) {
// 그 절반에 target이 있는 경우
right = middle - 1;
} else {
left = middle + 1;
}
} else {
// 절반 오른쪽이 정렬된 경우;
if (rotated[middle] < target && rotated[right] >= target) {
// 그 절반에 target이 있는 경우
left = middle + 1;
} else {
right = middle - 1;
}
}
}
return -1;
}
학습
중간 index와 왼쪽, 오른쪽 index를 설정하여 왼쪽에서 중간 인덱스 사이에 target이 있거나 중간 인덱스에서 오르쪽 인덱스 사이에 target이 발견되는지 확인하여 왼쪽, 오른쪽 index를 재설정하여 다시 같은 조회를 반복한다. while 반복문으로 진행할 수 있도록 한게 key였다.
O(logN)
이진트리의 총 노드에서 레벨을 하나씩 내려올 때마다 찾아야 하는 노드의 수는 전체 노드의 반으로 줄어든다.
M/2 개 => M/4 개 => M/8 개 => ...
Author And Source
이 문제에 관하여(Toy_ #14. rotatedArraySearch), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@jonghwan2_y/Toy-14.-rotatedArraySearch저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)