Interpolation Search ใน JavaScript

Interpolation Search คืออะไร

Interpolation Search เป็นอัลกอริทึมค้นหาในอาร์เรย์ที่ จัดเรียงแล้ว และมีการกระจายค่าที่ สม่ำเสมอ (Uniformly Distributed) เป็นการปรับปรุงจาก Binary Search โดยคาดเดาตำแหน่งเป้าหมายจากค่าที่ต้องการค้นหา แทนที่จะแบ่งครึ่งแบบคงที่

สูตรคำนวณตำแหน่ง

pos = lo + ((x - arr[lo]) * (hi - lo) / (arr[hi] - arr[lo]))

• arr[] - อาร์เรย์ที่จัดเรียงแล้ว
• x - ค่าที่ต้องการค้นหา
• lo - เริ่มต้นดัชนี
• hi - สิ้นสุดดัชนี

สูตรจะคืนค่า pos ใกล้ hi เมื่อ x ใกล้ arr[hi] และใกล้ lo เมื่อ x ใกล้ arr[lo]

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

const arr = [1, 4, 6, 7, 9, 12, 15, 16, 17, 23, 25, 26, 27, 31];
const target = 25;

const interpolationSearch = (arr = [], target) => {
  let left = 0;
  let right = arr.length - 1;
  
  while (left <= right) {
    const rangeDelta = arr[right] - arr[left];
    const indexDelta = right - left;
    const valueDelta = target - arr[left];
    
    // เป้าหมายน้อยกว่าค่าต่ำสุด
    if (valueDelta < 0) return -1;
    
    // ค่าทุกตัวเหมือนกัน (ป้องกันหารศูนย์)
    if (!rangeDelta) {
      return arr[left] === target ? left : -1;
    }
    
    // คำนวณตำแหน่งประมาณ
    const middleIndex = left + Math.floor((valueDelta * indexDelta) / rangeDelta);
    
    if (arr[middleIndex] === target) return middleIndex;
    
    if (arr[middleIndex] < target) {
      left = middleIndex + 1;
    } else {
      right = middleIndex - 1;
    }
  }
  return -1;
};

console.log(interpolationSearch(arr, target)); // 10

ผลลัพธ์

10

ความซับซ้อนและข้อจำกัด

• เร็วกว่า Binary Search เมื่อข้อมูลกระจายสม่ำเสมอ
• ช้ากว่า Binary Search เมื่อข้อมูลกระจายไม่สม่ำเสมอ (เช่น เพี้ยนมาก)
• ต้องการอาร์เรย์ที่จัดเรียงแล้วเท่านั้น