ইন্টারপোলেশন সার্চ (Interpolation Search)

বাইনারি সার্চ টেকনিকের জন্য, লিস্টগুলো সমান অংশে ভাগ হয়। ইন্টারপোলেশন সার্চিং টেকনিকের জন্য, প্রসিডিউর চেষ্টা করে ইন্টারপোলেশন ফর্মুলা ব্যবহার করে সঠিক পজিশন লোকেট করতে। অনুমানিত লোকেশন পাওয়ার পর, সেটি ব্যবহার করে লিস্টকে ভাগ করতে পারে। যেহেতু এটি প্রতিবার সঠিক লোকেশন খুঁজে বের করার চেষ্টা করে, তাই সার্চিং টাইম কমে। এই টেকনিক সহজে আইটেম খুঁজে পায় যদি আইটেমগুলো ইউনিফর্মলি ডিস্ট্রিবিউটেড থাকে।

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

• টাইম কমপ্লেক্সিটি: এভারেজ কেসে O(log₂(log₂ n)), এবং ওয়ার্স্ট কেসে O(n) (যখন আইটেমগুলো এক্সপোনেনশিয়ালি ডিস্ট্রিবিউটেড)
• স্পেস কমপ্লেক্সিটি: O(1)

ইনপুট এবং আউটপুট

Input: A sorted list of data: 10 13 15 26 28 50 56 88 94 127 159 356 480 567 689 699 780 850 956 995
The search key 780
Output: Item found at location: 16

অ্যালগরিদম

interpolationSearch(array, start, end, key)
Input - An sorted array, start and end location, and the search key
Output: location of the key (if found), otherwise wrong location.
Begin
    while start <= end AND key >= array[start] AND key <= array[end] do
        dist := key - array[start]
        valRange := array[end] - array[start]
        fraction := dist / valRange
        indexRange := end - start
        estimate := start + (fraction * indexRange)
        if array[estimate] = key then
            return estimate position
        if array[estimate] < key then
            start := estimate + 1
        else
            end = estimate - 1
        done
    return invalid position
End

উদাহরণ

#include 
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]; //range of value
        fraction = dist / valRange;
        indexRange = end - start;
        estimate = start + (fraction * indexRange); //estimated position of the key
        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 << "Enter number of items: ";
    cin >> n;
    int arr[n]; //create an array of size n
    cout << "Enter items: " << endl;
    for(int i = 0; i> arr[i];
    }
    cout << "Enter search key to search in the list: ";
    cin >> searchKey;
    if((loc = interpolationSearch(arr, 0, n-1, searchKey)) >= 0)
        cout << "Item found at location: " << loc << endl;
    else
        cout << "Item is not found in the list." << endl;
}

আউটপুট

Enter number of items: 20
Enter items:
10 13 15 26 28 50 56 88 94 127 159 356 480 567 689 699 780 850 956 995
Enter search key to search in the list: 780
Item found at location: 16