문제 소개
정렬된 숫자 배열(오름차순)과 찾고자 하는 목표값(target)을 입력받아, 이진 검색(Binary Search) 알고리즘을 활용해 해당 값의 인덱스를 반환하는 JavaScript 함수를 작성해야 합니다.
배열이 이미 정렬되어 있기 때문에 처음부터 끝까지 하나씩 확인하는 선형 검색(O(n))보다 훨씬 효율적인 이진 검색(O(log n))을 사용하는 것이 적합합니다. 만약 목표값이 배열에 존재하면 그 인덱스를 반환하고, 존재하지 않으면 -1을 반환하면 됩니다.
예를 들어 함수의 입력이 다음과 같다고 가정해 보겠습니다.
입력
const arr = [3, 5, 7, 9, 11, 13, 15, 16, 18, 21, 24, 25, 28]; const target = 13;
여기서 13은 인덱스 5에 위치하므로, 기대되는 출력은 다음과 같습니다.
출력
const output = 5;
이진 검색의 동작 원리
이진 검색은 다음과 같은 방식으로 작동합니다.
1. 검색 범위의 시작점(low)과 끝점(high)을 정합니다.
2. 범위의 중간 인덱스(middle)를 계산합니다.
3. 중간값이 목표값과 같으면 해당 인덱스를 반환합니다.
4. 중간값이 목표값보다 작으면 오른쪽 절반을, 크면 왼쪽 절반을 다시 검색합니다.
5. 시작점이 끝점보다 커지면 목표값이 없다는 의미이므로 -1을 반환합니다.
매 단계마다 검색 범위가 절반으로 줄어들기 때문에 시간 복잡도는 O(log n)으로 매우 효율적입니다.
구현 예제
재귀 함수를 활용한 전체 코드는 다음과 같습니다.
const arr = [3, 5, 7, 9, 11, 13, 15, 16, 18, 21, 24, 25, 28];
const target = 13;
const binarySearch = (arr = [], target) => {
const helper = (low, high) => {
// 검색 범위가 역전되면 값을 찾지 못한 것
if (low > high) {
return -1
}
const middle = Math.floor((low + high) / 2)
if (arr[middle] === target) {
return middle
} if (arr[middle] < target) {
// 목표값이 더 크면 오른쪽 절반 탐색
return helper(middle + 1, high)
}
// 목표값이 더 작으면 왼쪽 절반 탐색
return helper(low, middle - 1)
}
return helper(0, arr.length - 1)
};
console.log(binarySearch(arr, target));실행 결과
5
마무리 및 참고 사항
위 코드는 재귀(recursion) 방식으로 구현되었지만, while 반복문을 사용하면 스택 오버플로 걱정 없이 동일한 로직을 반복(iterative) 방식으로 구현할 수도 있습니다. 또한 중간 인덱스를 계산할 때 (low + high) / 2 대신 low + Math.floor((high - low) / 2)를 사용하면 매우 큰 배열에서 발생할 수 있는 정수 오버플로 문제를 예방할 수 있습니다.
이진 검색은 데이터베이스 인덱싱, 정렬된 로그 탐색 등 실무에서도 널리 활용되는 필수 알고리즘이므로, 동작 원리와 구현 방식을 모두 익혀두는 것이 좋습니다.