ইন্টারপোলেশন সার্চ
ইন্টারপোলেশন সার্চ হলো একটি অ্যালগরিদম যা কী-ভ্যালু অনুযায়ী ক্রমবদ্ধ করা একটি অ্যারেতে একটি কী খুঁজে বের করার জন্য ব্যবহৃত হয়।
উদাহরণস্বরূপ:
ধরুন, আমাদের কাছে n সংখ্যক ইউনিফর্মলি ডিস্ট্রিবিউটেড ভ্যালুয়ुक्त একটি সর্টেড অ্যারে arr[] আছে, এবং আমাদের একটি নির্দিষ্ট এলিমেন্ট target খুঁজে বের করতে হবে।
এটি নিচের অপারেশনগুলো করে পজিশন খুঁজে বের করে:
// ফর্মুলার আইডিয়া হলো pos-র একটি উচ্চতর মান রিটার্ন করা
// যখন সার্চ করা এলিমেন্ট arr[hi]-এর কাছাকাছি। এবং
// arr[lo]-এর কাছাকাছি হলে ছোট মান।
pos = lo + ((x - arr[lo]) * (hi - lo) / (arr[hi] - arr[Lo]))
কীগুলো:
arr[] - যেখানে এলিমেন্ট সার্চ করতে হবে
x - সার্চ করার এলিমেন্ট
lo - arr[]-এ শুরুতে ইন্ডেক্স
hi - 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));আউটপুট
কনসোলে নিচের আউটপুট পাওয়া যাবে:
10
