Nhảy tìm kiếm

Kỹ thuật tìm kiếm nhảy cũng hoạt động đối với danh sách có thứ tự. Nó tạo ra một khối và cố gắng tìm phần tử trong khối đó. Nếu mục không nằm trong khối, nó sẽ dịch chuyển toàn bộ khối. Kích thước khối dựa trên kích thước của danh sách. Nếu kích thước của danh sách là n thì kích thước khối sẽ là √n. Sau khi tìm thấy một khối chính xác, nó sẽ tìm mục bằng kỹ thuật tìm kiếm tuyến tính. Tìm kiếm nhảy nằm giữa tìm kiếm tuyến tính và tìm kiếm nhị phân tùy theo hiệu suất của nó.

Sự phức tạp của Kỹ thuật Tìm kiếm Nhảy

• Độ phức tạp về thời gian:O (√n)
• Độ phức tạp của không gian:O (1)

Đầu vào và Đầu ra

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

Thuật toán

jumpSearch(array, size, key)

Đầu vào: Mảng được sắp xếp, kích thước của mảng và khóa tìm kiếm

Đầu ra - vị trí của chìa khóa (nếu được tìm thấy), nếu không thì sai vị trí.

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

Ví dụ

#include<iostream>
#include<cmath>

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<end; i++) { //perform linear search in selected block
      if(array[i] == key)
         return i; //the correct position of the key
   }
   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< n; i++) {
      cin >> 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;
}

Đầu ra

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