이진 탐색은 정렬된 배열에서 원하는 값을 효율적으로 찾아내는 대표적인 알고리즘입니다. 매 단계마다 탐색 범위를 절반으로 줄여나가기 때문에 시간 복잡도가 O(log n)으로, 배열의 크기가 클수록 선형 탐색에 비해 압도적인 성능 차이를 보입니다.
binarySearch() 함수 설계
먼저 binarySearch()라는 함수를 만들어 보겠습니다. 이 함수는 다음과 같이 4개의 인자를 받습니다.
- 정렬된 숫자 또는 문자열 리터럴 배열
- 배열의 시작 인덱스 (0)
- 배열의 끝 인덱스 (length - 1)
- 검색할 값(숫자)
함수의 작동 방식은 다음과 같습니다.
- 배열 내에서 해당 값이 존재하면 그 값의 인덱스를 반환합니다.
- 존재하지 않으면 -1을 반환합니다.
전체 코드 예제
const arr = [2,4,6,6,8,8,9,10,13,15,17,21,24,26,28,36,58,78,90];
// 이진 탐색 함수
// 값을 찾으면 해당 요소의 인덱스를, 찾지 못하면 -1을 반환
const binarySearch = (arr, start, end, num) => {
const mid = start + Math.floor((end - start)/2);
if(start <= end){
if(arr[mid] === num){
return mid;
}
if(num < arr[mid]){
return binarySearch(arr, start, mid-1, num);
}
if(num > arr[mid]){
return binarySearch(arr, mid+1, end, num);
}
}
return -1;
};
console.log(binarySearch(arr, 0, arr.length-1, 13));
console.log(binarySearch(arr, 0, arr.length-1, 11));코드 동작 원리
이 알고리즘의 핵심은 중간 지점(mid)을 계산하는 부분입니다. start + Math.floor((end - start)/2) 공식을 사용하면 큰 배열에서도 오버플로우 없이 안전하게 중간 인덱스를 구할 수 있습니다.
- 중간 위치의 값이 찾고자 하는 값과 일치하면 해당 인덱스를 즉시 반환합니다.
- 찾는 값이 중간값보다 작으면 탐색 범위를 왼쪽 절반(
start ~ mid-1)으로 좁혀 재귀 호출합니다. - 찾는 값이 중간값보다 크면 오른쪽 절반(
mid+1 ~ end)으로 좁혀 재귀 호출합니다. - 시작 인덱스가 끝 인덱스보다 커지면 더 이상 탐색할 범위가 없으므로 -1을 반환합니다.
실행 결과
위 코드를 실행하면 콘솔에 다음과 같은 결과가 출력됩니다.
8 -1
첫 번째 호출에서는 값 13이 배열의 인덱스 8에 위치하고 있으므로 8이 출력되고, 두 번째 호출에서는 값 11이 배열에 존재하지 않으므로 -1이 출력됩니다.
마무리
이처럼 이진 탐색은 재귀 또는 반복문으로 간단하게 구현할 수 있으며, 정렬된 데이터에서 특정 값을 빠르게 찾아야 하는 상황에서 매우 유용하게 활용됩니다. 참고로 반복문(while 루프) 기반 구현은 재귀 호출에 따른 스택 오버플로우 위험이 없어 아주 큰 배열을 다룰 때 더 안전한 선택이 될 수 있습니다.