검색 차단
이진 검색과 마찬가지로 블록 검색도 정렬된 배열에 대한 검색 알고리즘입니다. 기본 아이디어는 고정된 단계로 건너뛰거나 모든 요소를 검색하는 대신 일부 요소를 건너뛰어 선형 검색보다 적은 수의 요소를 확인하는 것입니다.
예를 들어
길이가 n인 배열 arr와 크기가 m인 블록(점프할)이 있다고 가정합니다. 그런 다음 인덱스 arr[0], arr[m], arr[2 * m], ..., arr[k * m] 등에서 검색합니다.
arr[k * m]
이 알고리즘의 시간 복잡도는 -
다음은 코드입니다 -
다음은 콘솔의 출력입니다 -O(√n)
예시
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));
let blockStart = 0
let currentStep = step;
while (arr[Math.min(currentStep, len) - 1] < target) {
blockStart = currentStep;
currentStep += step;
if (blockStart >= len)
return -1;
}
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)); 출력
10