문제 개요
정렬된 배열을 첫 번째 인수로, 검색하고자 하는 쿼리 값을 두 번째 인수로 받는 JavaScript 함수를 작성해야 합니다. 이 함수는 이진 검색(Binary Search) 알고리즘을 활용하여 해당 쿼리가 배열 안에 존재하는지 여부를 판별합니다.
쿼리가 배열에 존재하면 그 요소의 인덱스를 반환하고, 존재하지 않으면 -1을 반환하도록 구현합니다.
이진 검색은 정렬된 배열에서만 동작하는 알고리즘으로, 배열의 중간값과 쿼리를 비교한 뒤 탐색 범위를 절반씩 줄여 나가는 방식입니다. 따라서 선형 검색의 O(n)보다 훨씬 빠른 O(log n)의 시간 복잡도를 가집니다.
예제 코드
재귀 호출 방식으로 구현한 코드는 다음과 같습니다.
const arr = [1, 2, 3, 5, 6, 7, 10, 11, 14, 15, 17, 19, 20, 22, 23];
const binarySearch = (arr, query) => {
let index = Math.floor(arr.length / 2);
if (arr[index] === query){
return index;
}else if (arr.length === 1){
return null;
}else if (arr[index] < query) {
arr = arr.slice(index + 1);
let res = binarySearch(arr, query);
if (res === null){
return -1;
}else {
return index + 1 + res;
};
}else {
let arr1 = arr.slice(0, index);
return binarySearch(arr1, query);
};
};
console.log(binarySearch(arr, 1));
console.log(binarySearch(arr, 7));
console.log(binarySearch(arr, 11));
console.log(binarySearch(arr, 12));
console.log(binarySearch(arr, 22));
동작 원리
이 함수는 다음 순서로 동작합니다.
1. 배열의 중간 인덱스를 계산합니다.
2. 중간값이 쿼리와 일치하면 해당 인덱스를 즉시 반환합니다.
3. 배열 길이가 1인데도 일치하지 않으면 null을 반환하여 탐색 실패를 알립니다.
4. 중간값이 쿼리보다 작으면 오른쪽 절반을 잘라내어 재귀 호출하고, 이때 잘라낸 만큼의 오프셋(index + 1)을 결과에 더해 원래 배열 기준의 인덱스를 보정합니다.
5. 중간값이 쿼리보다 크면 왼쪽 절반만 남겨 다시 재귀 호출합니다.
실행 결과
콘솔에 출력되는 결과는 다음과 같습니다.
0
5
7
-1
13
배열에 존재하는 값(1, 7, 11, 22)은 각각의 인덱스가 반환되고, 존재하지 않는 값(12)에 대해서는 -1이 반환되는 것을 확인할 수 있습니다.