บล็อกการค้นหา
เช่นเดียวกับการค้นหาไบนารี 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