Chặn tìm kiếm
Cũng giống như Tìm kiếm nhị phân, Tìm kiếm theo khối cũng là một thuật toán tìm kiếm các mảng đã được sắp xếp. Ý tưởng cơ bản là kiểm tra ít phần tử hơn (so với tìm kiếm tuyến tính) bằng cách nhảy lên trước bằng các bước cố định hoặc bỏ qua một số phần tử thay vì tìm kiếm tất cả các phần tử.
Ví dụ
Giả sử chúng ta có một mảng arr có độ dài n và khối (sẽ được nhảy) có kích thước m. Sau đó, chúng tôi tìm kiếm tại các chỉ mục arr [0], arr [m], arr [2 * m], ..., arr [k * m], v.v.
Khi chúng tôi tìm thấy khoảng arr [k * m]
Độ phức tạp về thời gian của thuật toán này là -
Sau đây là mã -
Sau đây là kết quả trên bảng điều khiển - O(√n)
Ví dụ
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)); Đầu ra
10