এক্সপোনেনশিয়াল সার্চ (Exponential Search)

এক্সপোনেনশিয়াল সার্চকে ডাবলিং বা গ্যালপিং সার্চও বলা হয়। এই মেকানিজমটি সার্চ কী কোথায় থাকতে পারে সে রেঞ্জ খুঁজে বের করতে ব্যবহৃত হয়। যদি L এবং U লিস্টের আপার ও লোয়ার বাউন্ড হয়, তবে L এবং U উভয়ই ২-এর ঘাত। লাস্ট সেকশনের জন্য, U হল লিস্টের লাস্ট পজিশন। সেজন্য এটি এক্সপোনেনশিয়াল নামে পরিচিত।

স্পেসিফিক রেঞ্জ পাওয়ার পর, এটি বাইনারি সার্চ টেকনিক ব্যবহার করে সার্চ কীয়ের সঠিক লোকেশন খুঁজে বের করে।

এক্সপোনেনশিয়াল সার্চ টেকনিকের কমপ্লেক্সিটি

• টাইম কমপ্লেক্সিটি: বেস্ট কেসে O(1)। এভারেজ বা ওয়ার্স্ট কেসে O(log₂ i)। যেখানে i হল সার্চ কী উপস্থিত লোকেশন।
• স্পেস কমপ্লেক্সিটি: 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

অ্যালগরিদম

binarySearch(array, start, end, key)

ইনপুট: একটি সোর্টেড অ্যারে, স্টার্ট এবং এন্ড লোকেশন, এবং সার্চ কী

আউটপুট - কীর লোকেশন (যদি পাওয়া যায়), অন্যথায় ভুল লোকেশন।

Begin
    if start <= end then
        mid := start + (end - start) / 2
        if array[mid] = key then
            return mid location
        if array[mid] > key then
            call binarySearch(array, mid+1, end, key)
        else when array[mid] < key then
            call binarySearch(array, start, mid-1, key)
    else
        return invalid location
End

exponentialSearch(array, start, end, key)

ইনপুট: একটি সোর্টেড অ্যারে, স্টার্ট এবং এন্ড লোকেশন, এবং সার্চ কী

আউটপুট: কীর লোকেশন (যদি পাওয়া যায়), অন্যথায় ভুল লোকেশন।

Begin
    if (end - start) <= 0 then
        return invalid location
    i := 1
    while i < (end - start) do
        if array[i] < key then
            i := i * 2 //increase i as power of 2
        else
            terminate the loop
        done
    call binarySearch(array, i/2, i, key)
End

উদাহরণ

#include 
using namespace std;
int binarySearch(int array[], int start, int end, int key) {
    if(start <= end) {
        int mid = (start + (end - start) / 2); //mid location of the list
        if(array[mid] == key)
            return mid;
        if(array[mid] > key)
            return binarySearch(array, start, mid-1, key);
        return binarySearch(array, mid+1, end, key);
    }
    return -1;
}
int exponentialSearch(int array[], int start, int end, int key) {
    if((end - start) <= 0)
        return -1;
    int i = 1; // as 2^0 = 1
    while(i < (end - start)) {
        if(array[i] < key)
            i *= 2; //i will increase as power of 2
        else
            break; //when array[i] crosses the key element
    }
    return binarySearch(array, i/2, i, key); //search item in the smaller range
}
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 = exponentialSearch(arr, 0, n, 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