Tìm kiếm khối (Block Search)
Giống như Tìm kiếm nhị phân, Tìm kiếm khối cũng là một thuật toán tìm kiếm cho các mảng đã 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 앞 theo bước cố định hoặc bỏ qua một số phần tử thay vì tìm kiếm tất cả.
Ví dụ:
Giả sử chúng ta có mảng arr độ dài n và kích thước khối (để nhảy) là m. Sau đó chúng ta tìm kiếm tại các chỉ số arr[0], arr[m], arr[2 * m], ..., arr[k * m] và cứ thế.
Khi tìm thấy khoảng arr[k * m] < x < arr[(k+1) * m], chúng ta thực hiện tìm kiếm tuyến tính từ chỉ số k * m để tìm phần tử x.
Độ phức tạp thời gian của thuật toán này là:
O(√n)
Ví dụ
Dưới đây là mã nguồ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));Kết quả
Đầu ra trên console:
10