บล็อกการค้นหา
เช่นเดียวกับการค้นหาไบนารี Block Search ยังเป็นอัลกอริธึมการค้นหาสำหรับอาร์เรย์ที่จัดเรียง แนวคิดพื้นฐานคือการตรวจสอบองค์ประกอบให้น้อยลง (มากกว่าการค้นหาเชิงเส้น) โดยการกระโดดไปข้างหน้าด้วยขั้นตอนคงที่หรือข้ามองค์ประกอบบางอย่างแทนการค้นหาองค์ประกอบทั้งหมด
ตัวอย่าง
สมมติว่าเรามีอาร์เรย์ arr ยาว n และบล็อก (ที่จะกระโดด) ขนาด 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
