그 인덱스에 있는 값
문제 설명
배열과 숫자 하나를 전달받는 search 함수는 해당 숫자의 인덱스에 해당하는 값을 반환한다. 전달받은 숫자에 해당하는 인덱스에 값이 존재하지 않을 경우 -1을 반환한다. 전달받은 배열은 정렬되어 있다.
입력 예시는 다음과 같다
search([1, 2, 3, 4, 5, 6], 4) // 3
search([1, 2, 3, 4, 5, 6], 6) // 5
search([1, 2, 3, 4, 5, 6], 11) // -1
이 문제를 일반적으로 배열에 대해 루프를 전체적으로 한번씩 돌아, 배열이 처음부터 끝까지 돌며 해당 숫자를 찾는 방식은 시간복잡도가 O(n)을 가지게 된다.
즉 전체 배열을 한번 훑어보고 찾거나 못 찾거나 둘 중 하나이다.
이에 대한 단순한 해결책은 다음과 같다.
function search(arr, val) {
for (let i = 0; i < arr.length; i++) {
if (arr[i] === val) {
return i;
}
}
return -1;
};
하나의 루프를 가지고 O(n)의 시간 복잡도를 가진다. 이러한 구졸르 선형 탐색이라고 한다.
우리가 이번에 살펴보고자 하는 것은 약간 다르다. 이진 탐색을 이용하여 문제를 풀어볼 것인데, 이는 분할과 정복 알고리즘을 이용하는 방법이다.
소스 코드는 다음과 같다.
function search(array, val) {
let min = 0;
let max = array.length - 1;
while (min <= max) {
// 배열의 중간값을 취한다.
let middle = Math.floor((min + max) / 2);
let currentElement = array[middle];
// middle을 val과 비교하며 최신화한다.
// 효율적인 탐색을 위해 값이 존재하지 않을 부분은 바로 무시하는 방식을 취한다.
if (array[middle] < val) {
min = middel + 1;
}
else if (array[middle] > val) {
max = middle - 1;
}
else {
// middle의 값이 val과 같다면 리턴한다.
return middle;
}
}
// val에 해당하는 값이 없다면 -1을 리턴한다.
return -1;
};
위와 같이 분할 정복 알고리즘으로 시간을 절약할 수 있다. 위 소스 코드의 시간복잡도는 Ologn 이다.
Author And Source
이 문제에 관하여(그 인덱스에 있는 값), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@alsghk9701/그-인덱스에-있는-값저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)