介绍

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

描述

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

1. 从第一个元素开始设置 i 为 0，块大小 m 为 √n 。
2. 当 A[min(m,n)-1]<X 且 i<n 时。

• 将 i 设为 m，并以√n 递增 m。

3. If i >= n return -1。
4. 当 A[i]< X 时，执行以下操作。

• 递增 i
• 如果 i 等于 min (m,n) 返回 -1。

5. 如果 A[i] == X ，返回 i。
6. 否则，返回 -1。

假设我们有一个数组 arr []，其大小为 n, block (向前跳过的固定长度) 的大小为 m。然后我们搜索索引 arr[0] ， arr[m] ， arr[2m]…Arr [km] 等。一旦我们找到区间 ( arr[km] < x < arr[(k+1)m] )，我们就从索引 km 执行线性搜索操作来找到元素。

块的大小

在最坏的情况下，如果最后检查的值大于要查找的元素，必须跳 n/m 次，然后再执行线性查找 m-1 次。因此最坏情况下的比较总数为 ((n/m) + m-1) 。

当 m =√n 时，函数 ((n/m) + m-1) 的值最小。因此，最佳步长为 m =√n 即数组长度的平方根 。

复杂度

时间复杂度

• 平均情况 跳跃排序算法运行 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)，因为除了临时变量外，它不需要任何数据结构。

实现

JavaScript

/* The Jump Search algorithm allows to combine a linear search with a speed optimization.
  * This means that instead of going 1 by 1, we will increase the step of √n and increase that
  * step of √n which make the step getting bigger and bigger.
  * The asymptotic analysis of Jump Search is o(√n). Like the binary search, it needs to be sorted.
  * The advantage against binary search is that Jump Search traversed back only once.
 */

const jumpSearch = (arr, value) => {
  const length = arr.length
  let step = Math.floor(Math.sqrt(length))
  let lowerBound = 0
  while (arr[Math.min(step, length) - 1] < value) {
    lowerBound = step
    step += step
    if (lowerBound >= length) {
      return -1
    }
  }

  const upperBound = Math.min(step, length)
  while (arr[lowerBound] < value) {
    lowerBound++
    if (lowerBound === upperBound) {
      return -1
    }
  }
  if (arr[lowerBound] === value) {
    return lowerBound
  }
  return -1
}

CPP

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

参考

• Jump search - Wikipedia (opens new window)