Block Search (การค้นหาแบบบล็อก) ใน JavaScript

Block Search คืออะไร

Block Search (หรือ Jump Search) เป็นอัลกอริทึมค้นหาในอาร์เรย์ที่ จัดเรียงแล้ว คล้าย Binary Search แต่กระโดดข้ามข้อมูลเป็นบล็อกขนาดคงที่ แทนการแบ่งครึ่ง

แนวคิด

• ขนาดบล็อก m = √n (รากที่สองของความยาวอาร์เรย์) - ค่าที่เหมาะสมที่สุด
• ตรวจสอบที่ดัชนี: arr[0], arr[m], arr[2m], arr[3m]...
• เมื่อพบช่วงที่ arr[km] < target < arr[(k+1)m] ให้ Linear Search ในบล็อกนั้น

โค้ดตัวอย่าง

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)); // ขนาดบล็อก = √n
  let blockStart = 0;
  let currentStep = step;
  
  // กระโดดหาบล็อกที่มีเป้าหมาย
  while (arr[Math.min(currentStep, len) - 1] < target) {
    blockStart = currentStep;
    currentStep += step;
    if (blockStart >= len) return -1;
  }
  
  // Linear Search ในบล็อกที่พบ
  while (arr[blockStart] < target) {
    blockStart++;
    if (blockStart == Math.min(currentStep, len)) return -1;
  }
  
  return arr[blockStart] === target ? blockStart : -1;
};

console.log(blockSearch(arr, target));

ผลลัพธ์

10

ความซับซ้อน

เปรียบเทียบอัลกอริทึมค้นหา

* Average case

เมื่อไหร่ควรใช้ Block Search

• ข้อมูลจัดเรียงแล้วแต่ Binary Search ใช้ไม่ได้ (เช่น Linked List)
• การเข้าถึงแบบ Random Access มีค่าใช้จ่ายสูง
• ต้องการอัลกอริทึมที่เข้าใจง่ายกว่า Binary Search