ข้ามการค้นหา

เทคนิคการค้นหาแบบข้ามยังใช้ได้กับรายการที่เรียงลำดับด้วย มันสร้างบล็อกและพยายามค้นหาองค์ประกอบในบล็อกนั้น หากรายการไม่อยู่ในบล็อก รายการจะเลื่อนทั้งบล็อก ขนาดบล็อกขึ้นอยู่กับขนาดของรายการ หากขนาดของรายการเป็น n ขนาดบล็อกจะเป็น √n หลังจากพบบล็อกที่ถูกต้องแล้ว จะพบรายการโดยใช้เทคนิคการค้นหาเชิงเส้น การค้นหาแบบข้ามอยู่ระหว่างการค้นหาเชิงเส้นและการค้นหาแบบไบนารีตามประสิทธิภาพ

ความซับซ้อนของเทคนิค Jump Search

• ความซับซ้อนของเวลา: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)

ป้อนข้อมูล: อาร์เรย์ที่จัดเรียง ขนาดของอาร์เรย์และคีย์การค้นหา

ผลลัพธ์ − ตำแหน่งของกุญแจ (หากพบ) มิฉะนั้น ตำแหน่งที่ไม่ถูกต้อง

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<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;
}

ผลลัพธ์

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