정렬된 배열(오름차순이든 내림차순이든)을 다룰 때는 이진 탐색(Binary Search)이 가장 최적화되고 효율적인 탐색 알고리즘입니다. 이진 탐색은 배열의 중간 요소를 기준으로 탐색 범위를 절반씩 줄여 나가는 방식으로 동작하기 때문에, 시간 복잡도가 O(log n)으로 선형 탐색(O(n))보다 훨씬 빠릅니다.
이번 글에서는 정렬된 리터럴 배열에서 특정 대상(target) 값을 찾는 이진 탐색 함수를 작성하고, 이를 Array 객체의 prototype 속성에 연결하여 어떤 배열에서든 바로 호출할 수 있도록 만들어 보겠습니다.
이진 탐색의 동작 원리
이진 탐색은 다음 순서로 진행됩니다.
- 배열의 시작 인덱스(start)와 끝 인덱스(end)를 설정합니다.
- 두 인덱스 사이의 중간 지점(mid)에 있는 값을 확인합니다.
- 중간 값이 찾으려는 값보다 작으면 시작점을 중간으로 이동하고, 크면 끝점을 중간으로 이동시켜 탐색 범위를 절반으로 줄입니다.
- 값을 찾거나 더 이상 탐색할 범위가 없을 때까지 반복합니다.
예제 코드
아래 코드는 이진 탐색 함수를 Array.prototype에 추가한 예제입니다.
const arr = [2, 5, 8, 12, 14, 16, 17, 22, 26, 28, 35, 67, 78, 99];
const target = 22;
Array.prototype.binarySearch = function(target) {
if (!this.length) { return false; }
if (this[0] === target) { return true; }
var i, mid,
start = 0,
end = this.length,
c = false;
while (c = (i = this[mid = start + ((end - start) >> 1)]) !== target) {
i < target ? (start = mid) : (end = mid);
if (start >= end - 1) { break; }
}
return !c;
};
console.log(arr.binarySearch(target));
출력 결과
콘솔에 출력되는 결과는 다음과 같습니다.
true
배열 [2, 5, 8, 12, 14, 16, 17, 22, ...] 안에 22가 실제로 존재하므로 true가 출력됩니다. 반대로 배열에 없는 값을 검색하면 false가 반환됩니다.
마무리
이처럼 이진 탐색을 Array.prototype에 한 번만 정의해 두면, 정렬된 모든 배열에서 arr.binarySearch(값) 형태로 간편하게 재사용할 수 있습니다. 단, 이진 탐색은 반드시 정렬된 배열에서만 올바르게 동작한다는 점을 기억하세요. 데이터가 정렬되어 있지 않다면 먼저 sort() 메서드로 정렬한 뒤 사용하는 것이 좋습니다.