跳跃查找

搜索算法

在有序数组中,通过跳跃固定步长来缩小查找范围,然后在确定的区间内进行线性查找。结合了二分查找和线性查找的优点。

时间复杂度:最佳 O(1) | 平均 O(√n) | 最差 O(√n)
空间复杂度:O(1)

应用场景/前提条件

  • 数组必须是有序的
  • 较适合大型数据集

算法讲解

跳跃查找

介绍

跳跃查找(Jump Search)是一种在有序数组中查找元素的算法,核心思想是通过跳过固定步长的元素来缩小搜索范围,然后在缩小的区间内进行线性查找。跳跃查找是二分查找和线性查找的混合体,特别适合大型有序数据集。

跳跃查找的效率取决于步长的选择。在最佳情况下,跳跃查找的时间复杂度可以达到 O(√n),优于线性查找的 O(n),但不如二分查找的 O(log n)。但是在一些具体场景下,跳跃查找比二分查找表现更好,比如当内存中访问顺序元素比随机访问更高效的时候。

算法步骤

  1. 确定跳跃步长(通常取 √n,n 是数组长度)
  2. 从数组开头开始,每次跳过步长个元素,直到找到大于或等于目标值的元素或达到数组末尾
  3. 如果找到的元素大于目标值,则回退一步,在该区间内进行线性查找
  4. 如果找到目标值,返回其索引;否则返回未找到标识

核心特性

  • 分块查找:将数组分成大小为 √n 的块,跳跃式地查找
  • 步长选择:最优步长为 √n,使跳跃次数与块内线性查找次数取得平衡(空间复杂度始终为 O(1),与步长无关)
  • 时间复杂度:平均情况为 O(√n)

...