ค้นหาการแก้ไขใน JavaScript

การค้นหาการแก้ไข

Interpolation search คืออัลกอริธึมสำหรับค้นหาคีย์ในอาร์เรย์ที่เรียงตามค่าตัวเลขที่กำหนดให้กับคีย์ (ค่าคีย์)

ตัวอย่าง

สมมติว่าเรามีอาร์เรย์ที่เรียงลำดับของ n ค่าที่กระจายอย่างสม่ำเสมอ arr[] และเราจำเป็นต้องเขียนฟังก์ชันเพื่อค้นหาเป้าหมายขององค์ประกอบเฉพาะในอาร์เรย์

มันดำเนินการดังต่อไปนี้เพื่อค้นหาตำแหน่ง -

// แนวคิดของสูตรคือการคืนค่า pos ที่สูงกว่า

// เมื่อองค์ประกอบที่จะค้นหาอยู่ใกล้กับ arr[hi] และ

// ค่าน้อยกว่าเมื่ออยู่ใกล้ arr[lo]

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

กุญแจ −

arr[] - อาร์เรย์ที่ต้องค้นหาองค์ประกอบ
x - องค์ประกอบที่ต้องการค้นหา
แท้จริง - ดัชนีเริ่มต้นใน arr[]
สวัสดี - ดัชนีสิ้นสุดใน arr[]

เราจำเป็นต้องเขียนฟังก์ชัน JavaScript ที่รับอาร์เรย์ของตัวเลขเป็นอาร์กิวเมนต์แรก และค้นหาเป้าหมายเป็นอาร์กิวเมนต์ที่สอง

ฟังก์ชันนี้ควรใช้อัลกอริธึมการค้นหา Interpolation เพื่อค้นหาเป้าหมายในอาร์เรย์

ตัวอย่าง

ต่อไปนี้เป็นรหัส -

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));

ผลลัพธ์

ต่อไปนี้เป็นผลลัพธ์บนคอนโซล -