জাম্প সার্চ (Jump Search)

জাম্প সার্চ টেকনিকও অর্ডার্ড লিস্টের জন্য কাজ করে। এটি একটি ব্লক তৈরি করে এবং সেই ব্লকে এলিমেন্ট খুঁজে বের করার চেষ্টা করে। যদি আইটেম ব্লকে না থাকে, তবে পুরো ব্লকটি শিফট করে। ব্লক সাইজ লিস্টের সাইজের ওপর ভিত্তি করে। যদি লিস্টের সাইজ n হয় তবে ব্লক সাইজ হবে √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 356
Output: Item found at location: 11

অ্যালগরিদম

jumpSearch(array, size, key)
Input: An sorted array, size of the array and the search key
Output - location of the key (if found), otherwise wrong location.
Begin
    blockSize := √size
    start := 0
    end := blockSize
    while array[end] <= key AND end < size do
        start := end
        end := end + blockSize
        if end > size - 1 then
            end := size
        done
    for i := start to end -1 do
        if array[i] = key then
            return i
        done
    return invalid location
End

উদাহরণ

#include 
#include 
using namespace std;
int jumpSearch(int array[], int size, int key) {
    int start = 0;
    int end = sqrt(size); //the square root of array length
    while(array[end] <= key && end < size) {
        start = end; //it it is not correct block then shift block
        end += sqrt(size);
        if(end > size - 1)
            end = size; //if right exceeds then bound the range
    }
    for(int i = start; i> 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 = jumpSearch(arr, 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: 356
Item found at location: 11