跳跃搜索

1. 跳跃搜索算法
2. 跳跃搜索示例
3. 跳跃搜索算法的实现
4. 跳跃搜索算法的复杂度

跳跃搜索是一种区间搜索算法。它是一种相对较新的算法，只适用于排序数组。它试图比线性搜索减少所需的比较次数，不像线性搜索那样扫描每一个元素。在跳跃搜索中，数组被分成 m 块。它搜索一个块中的元素，如果该元素不存在，则移动到下一个块。当算法找到包含元素的块时，它使用线性搜索算法来寻找精确的索引。这种算法比线性搜索快，但比二叉搜索慢。

跳跃搜索算法

假设我们有一个未排序的数组 A[]，包含 n 个元素，我们想找到一个元素 X。

跳跃搜索示例

假设我们有一个数组：(1, 2, 3, 4, 5, 6, 7, 8, 9)，我们想找到 X-7。

因为有 9 个元素，所以我们把 n 设为 9。

跳跃搜索算法的实现

#include <bits/stdc++.h>
using namespace std;

int jumpSearch(int arr[], int x, int n) {
  int m = sqrt(n);
  int i = 0;
  while (arr[min(m, n) - 1] < x) {
    i = m;
    m += sqrt(n);
    if (i >= n) return -1;
  }
  while (arr[i] < x) {
    i++;
    if (i == min(m, n)) return -1;
  }
  if (arr[i] == x) return i;

  return -1;
}

int main() {
  int n = 10;
  int arr[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
  int x = 7;
  int result = jumpSearch(arr, x, n);
  if (result == -1)
    cout << "Element not found";
  else
    cout << "Element found at index " << result;
}

跳跃搜索算法的复杂度

时间复杂度

• 平均情况

跳跃排序算法运行 n/m 次，其中 n 是元素数量，m 是块大小。线性搜索需要 m-1 次比较，使得总时间表达式为 n/m+m-1。使时间表达式最小化的 m 的最优值为√n，使得时间复杂度为 n/√n+√n，即√n。跳跃搜索算法的时间复杂度为 O(√n)。

• 最佳情况

最佳情况下的时间复杂度是 O(1)。当要搜索的元素是数组中的第一个元素时，就会出现这种情况。

• 最坏情况

最坏的情况发生在我们做 n/m 跳跃的时候，我们最后检查的值大于我们要搜索的元素，m-1 比较进行线性搜索。最坏情况下的时间复杂度为 O(√n)。

空间复杂度

这种算法的空间复杂度是 O(1)，因为除了临时变量外，它不需要任何数据结构。