블록 검색(Block Search)이란?
이진 탐색(Binary Search)과 마찬가지로 블록 검색 역시 정렬된 배열을 대상으로 하는 탐색 알고리즘입니다. 핵심 아이디어는 모든 요소를 하나씩 확인하는 선형 탐색 대신, 고정된 크기만큼 앞으로 점프하거나 일부 요소를 건너뛰어 확인해야 할 요소의 개수를 크게 줄이는 것입니다.
동작 원리
예를 들어 길이가 n인 배열 arr과 점프할 블록 크기 m이 있다고 가정해 보겠습니다. 그러면 다음과 같은 인덱스를 차례대로 확인합니다.
arr[0] → arr[m] → arr[2 * m] → ... → arr[k * m]
확인 중에 arr[k * m] < x < arr[(k+1) * m] 조건을 만족하는 구간을 발견하면, 해당 블록 안에 목표 값 x가 존재한다는 의미입니다. 이후 k * m 인덱스부터 블록 끝까지 선형 탐색을 수행하여 x를 찾아냅니다.
이 알고리즘의 시간 복잡도는 다음과 같습니다.
O(√n)
선형 탐색의 O(n)보다 빠르며, 블록 크기를 √n으로 설정했을 때 최적의 성능을 얻을 수 있습니다.
JavaScript 구현 예제
다음은 블록 검색을 JavaScript로 구현한 코드입니다.
const arr = [1, 4, 6, 7, 9, 12, 15, 16, 17, 23, 25, 26, 27, 31];
const target = 25;
const blockSearch = (arr = [], target) => {
let { length: len } = arr;
let step = Math.floor(Math.sqrt(len)); // 블록 크기 = √n
let blockStart = 0;
let currentStep = step;
// 1단계: 블록 단위로 점프하며 목표 값이 속한 구간 찾기
while (arr[Math.min(currentStep, len) - 1] < target) {
blockStart = currentStep;
currentStep += step;
if (blockStart >= len)
return -1;
}
// 2단계: 해당 블록 내부에서 선형 탐색 수행
while (arr[blockStart] < target) {
blockStart++;
if (blockStart == Math.min(currentStep, len))
return -1;
}
// 결과 판별
if (arr[blockStart] == target)
return blockStart;
else
return -1;
};
console.log(blockSearch(arr, target));
코드 설명
- 블록 크기 계산:
Math.floor(Math.sqrt(len))로 배열 길이의 제곱근을 구해 최적의 점프 간격을 설정합니다. - 구간 탐색: 첫 번째 while 루프에서 블록 단위로 점프하며 목표 값이 포함된 구간을 좁혀 나갑니다.
- 선형 탐색: 두 번째 while 루프에서 해당 블록 내부를 처음부터 끝까지 확인합니다.
- 결과 반환: 값을 찾으면 해당 인덱스를, 찾지 못하면 -1을 반환합니다.
실행 결과
위 코드를 실행하면 콘솔에 다음과 같은 결과가 출력됩니다.
10
배열에서 값 25는 인덱스 10에 위치하므로, 블록 검색 함수가 올바르게 동작한 것을 확인할 수 있습니다.