跳转搜索

2023-06-21 05:09:02 85

跳转搜索技术也适用于有序列表。它创建一个块并尝试在该块中查找元素。如果项目不在块中，它会移动整个块。块大小基于列表的大小。如果列表的大小为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:
在以下位置找到的物品： 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
#include

using namespace std;
int jumpSearch(int array[], int size, int key) {
   int start = 0;
   int end = sqrt(size); //数组长度的平方根

   while(array[end] <= key && end < size) {
      start = end; //它不是正确的块然后移位块
      end += sqrt(size);
      if(end > size - 1)
         end = size; //如果权限超过则限制范围
   }

   for(int i = start; i> n;
   int arr[n]; //创建一个大小为n的数组
   cout << "输入项目： " << endl;

   for(int i = 0; i< n; i++) {
      cin >> arr[i];
   }

   cout << "输入搜索键在列表中搜索： ";
   cin >> searchKey;
   if((loc = jumpSearch(arr, n, searchKey)) >= 0)
      cout << "在以下位置找到的物品： " << loc << endl;
   else
      cout << "在列表中找不到项目。" << endl;
}

输出结果

输入项目数： 20
输入项目：
10 13 15 26 28 50 56 88 94 127 159 356 480 567 689 699 780 850 956 995
输入搜索键在列表中搜索： 356
在以下位置找到的物品： 11

跳转搜索

跳转搜索技术的复杂性

输入和输出

算法

示例

热门推荐

随机推荐