বাইনারি সার্চ টেকনিকে লিস্টগুলো সমান ভাগে ভাগ করা হয়। ইন্টারপোলেশন সার্চিং টেকনিকে, প্রসিডিউর ইন্টারপোলেশন ফর্মুলা ব্যবহার করে সঠিক পজিশন লোকেট করার চেষ্টা করে। অনুমানিত লোকেশন পাওয়ার পর, সেটি ব্যবহার করে লিস্টকে আলাদা করা যায়। যেহেতু এটি প্রতিবার সঠিক লোকেশন খুঁজে বের করার চেষ্টা করে, তাই সার্চিং টাইম কমে। এই টেকনিক সহজে আইটেম খুঁজে বের করতে পারে যদি আইটেমগুলো ইউনিফর্মলি ডিস্ট্রিবিউটেড থাকে।
ইন্টারপোলেশন সার্চ টেকনিকের জটিলতা
সময় জটিলতা: গড় কেসে O(log₂(log₂ n)), এবং ਵอasst কেসে O(n) (যখন আইটেমগুলো এক্সপোনেনশিয়ালি ডিস্ট্রিবিউটেড থাকে)
স্পেস জটিলতা: O(1)
ইনপুট − একটি সর্টেড ডেটা লিস্ট: 10 13 15 26 28 50 56 88 94 127 159 356 480 567 689 699 780 850 956 995। সার্চ কি 780 আউটপুট − আইটেম লোকেশন 16-এ পাওয়া গেলো
অ্যালগরিদম
interpolationSearch(array, start, end, key)
ইনপুট: একটি সর্টেড অ্যারে, শুরু এবং শেষ লোকেশন, এবং সার্চ কি
আউটপুট: কির লোকেশন (যদি পাওয়া যায়), অন্যথায় ভুল লোকেশন।
শুরু
যতক্ষণ start <= end AND key >= array[start] AND key <= array[end]
dist := key – array[start]
valRange := array[end] – array[start]
fraction := dist / valRange
indexRange := end – start
estimate := start + (fraction * indexRange)
যদি array[estimate] = key হয় তবে
estimate পজিশন ফেরত দাও
যদি array[estimate] < key হয় তবে
start := estimate + 1
অন্যথায়
end = estimate - 1
শেষ
invalid position ফেরত দাও
শেষ
উদাহরণ কোড
#include <iostream>
using namespace std;
int interpolationSearch(int array[], int start, int end, int key) {
int dist, valRange, indexRange, estimate;
float fraction;
while(start <= end && key >= array[start] && key <= array[end]) {
dist = key - array[start];
valRange = array[end] - array[start];
fraction = dist / valRange;
indexRange = end - start;
estimate = start + (fraction * indexRange);
if(array[estimate] == key) return estimate;
if(array[estimate] < key) start = estimate + 1;
else end = estimate - 1;
}
return -1;
}
int main() {
int n, searchKey, loc;
cout << "আইটেমের সংখ্যা দিন: ";
cin >> n;
int arr[n];
cout << "আইটেমগুলো দিন: " << endl;
for(int i = 0; i < n; i++) {
cin >> arr[i];
}
cout << "সার্চ কি দিন: ";
cin >> searchKey;
if((loc = interpolationSearch(arr, 0, n-1, searchKey)) >= 0)
cout << "আইটেম লোকেশন: " << loc << endl;
else
cout << "আইটেম লিস্টে পাওয়া যায়নি।" << endl;
}
আউটপুট
আইটেমের সংখ্যা দিন: 20 আইটেমগুলো দিন: 10 13 15 26 28 50 56 88 94 127 159 356 480 567 689 699 780 850 956 995 সার্চ কি দিন: 780 আইটেম লোকেশন: 16
