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

বাইনারী অনুসন্ধান কৌশলের জন্য, তালিকাগুলিকে সমান অংশে ভাগ করা হয়েছে৷ ইন্টারপোলেশন অনুসন্ধান কৌশলের জন্য, প্রক্রিয়াটি ইন্টারপোলেশন সূত্র ব্যবহার করে সঠিক অবস্থান সনাক্ত করার চেষ্টা করবে। আনুমানিক অবস্থান খোঁজার পরে, এটি সেই অবস্থান ব্যবহার করে তালিকাটি আলাদা করতে পারে। যেহেতু এটি প্রতিবার সঠিক অবস্থান খুঁজে বের করার চেষ্টা করে, তাই অনুসন্ধানের সময় হ্রাস পায়। আইটেমগুলি সমানভাবে বিতরণ করা হলে এই কৌশলটি সহজেই আইটেমগুলি খুঁজে পেতে পারে৷

ইন্টারপোলেশন সার্চ টেকনিকের জটিলতা

• সময়ের জটিলতা: গড় ক্ষেত্রের জন্য O(log2(log2 n)), এবং সবচেয়ে খারাপ ক্ষেত্রে 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 আউটপুট অবস্থান:It-এ পাওয়া গেছে 
অ্যালগরিদম
 
ইন্টারপোলেশন সার্চ (অ্যারে, শুরু, শেষ, কী)
 

 ইনপুট -  একটি সাজানো অ্যারে, শুরু এবং শেষ অবস্থান, এবং অনুসন্ধান কী
 

 আউটপুট: চাবির অবস্থান (যদি পাওয়া যায়), অন্যথায় ভুল অবস্থান।
 
শুরু করার সময় শুরু করুন <=শেষ এবং কী>=অ্যারে[স্টার্ট] এবং কী <=অ্যারে[এন্ড] ডিস্ট করুন :=কী – অ্যারে[স্টার্ট] ভ্যালরেঞ্জ :=অ্যারে[শেষ] – অ্যারে[স্টার্ট] ভগ্নাংশ :=dist / valRange indexRange :=শেষ - প্রারম্ভিক অনুমান :=start + (ভগ্নাংশ * indexRange) যদি array[estimate] =কী তারপর অ্যারে [estimate] <কী তারপর শুরু :=অনুমান + 1 অন্য শেষ =অনুমান -1 সম্পন্ন ফেরত অবৈধ অবস্থানশেষ
 
উদাহরণ
 
#include namespace ব্যবহার করে std;int interpolationSearch(int array[], int start, int end, int key) { int dist, valRange, indexRange, অনুমান; ভাসমান ভগ্নাংশ; while(start <=end &&key>=array[start] &&key <=array[end]) { dist =key - array[start]; valRange =array[end] - array[start]; // মানের ভগ্নাংশের পরিসর =dist / valRange; indexRange =শেষ - শুরু; অনুমান =শুরু + (ভগ্নাংশ * সূচক রেঞ্জ); //কীটির আনুমানিক অবস্থান যদি(অ্যারে[অনুমান] ==কী) রিটার্ন অনুমান; if(array[estimate] > n; int arr[n]; // আকারের একটি অ্যারে তৈরি করুন n cout <<"আইটেমগুলি লিখুন:" <> arr[i]; } cout <<"তালিকায় অনুসন্ধান করতে অনুসন্ধান কী লিখুন:"; cin>> searchKey; if((loc =interpolationSearch(arr, 0, n-1, searchKey))>=0) cout <<"স্থানে আইটেম পাওয়া গেছে:" < 
আউটপুট
 
আইটেমের সংখ্যা লিখুন:20টি আইটেম লিখুন:10 13 15 26 28 50 56 88 94 127 159 356 480 567 689 699 780 850 956 995 প্রবেশ করুন:অনুসন্ধান কী লিখুন:6 নম্বর তালিকাতে সন্ধান করুন:7টি তালিকার মধ্যে সন্ধান করুন