জাভাস্ক্রিপ্টে ইন্টারপোলেশন অনুসন্ধান

ইন্টারপোলেশন অনুসন্ধান

ইন্টারপোলেশন অনুসন্ধান হল একটি অ্যারেতে একটি কী অনুসন্ধান করার জন্য একটি অ্যালগরিদম যা কীগুলিকে (কী মান) বরাদ্দ করা সংখ্যাসূচক মান দ্বারা ক্রম করা হয়েছে।

উদাহরণস্বরূপ

ধরুন, আমাদের একটি সাজানো অ্যারে আছে n অভিন্নভাবে বিতরণ করা মান arr[], এবং অ্যারেতে একটি নির্দিষ্ট উপাদান লক্ষ্য অনুসন্ধানের জন্য আমাদের একটি ফাংশন লিখতে হবে।

এটি অবস্থান খুঁজে পেতে নিম্নলিখিত ক্রিয়াকলাপগুলি করে −

// সূত্রের ধারণা হল pos এর উচ্চতর মান ফেরত দেওয়া

// যখন অনুসন্ধান করা উপাদান arr[hi] এর কাছাকাছি হয়। এবং

arr[lo]

-এর কাছাকাছি হলে // ছোট মান

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

কী -

arr[] - অ্যারে যেখানে উপাদানগুলি অনুসন্ধান করা প্রয়োজন
x - উপাদান অনুসন্ধান করা হবে
lo - সূচনা সূচী arr []
হাই - এন্ডিং ইনডেক্স এআরআর[]

আমাদের একটি জাভাস্ক্রিপ্ট ফাংশন লিখতে হবে যা প্রথম আর্গুমেন্ট হিসাবে সংখ্যার অ্যারে এবং দ্বিতীয় আর্গুমেন্ট হিসাবে একটি সার্চ টার্গেট নেয়৷

অ্যারেতে লক্ষ্য অনুসন্ধানের জন্য ফাংশনটি ইন্টারপোলেশন অনুসন্ধান অ্যালগরিদম ব্যবহার করা উচিত।

উদাহরণ

নিম্নলিখিত কোড -

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

আউটপুট

নিম্নোক্ত কনসোলে আউটপুট -