跳跃查找算法-C

跳跃查找是在有序数组中用到的一种搜索算法,就像二分查找,当然二分查找用的更频繁。跳跃查找的洋文:Jump Search/Block Search,参考Wiki

跳跃查找算法和线性查找类似,只是它以一个固定的步长跳跃搜索。如下图

跳跃查找算法
在有序数组中查找55

  1. 从索引0跳到索引4 (55>3)
  2. 从索引4跳到索引8 (55>21)
  3. 从索引8跳到索引12 (55<144)
  4. 由于144大于55,跳回索引9
  5. 从索引9处执行线性查找,找到55

由于跳跃查找需要跳跃固定步长。那么,步长设置多少合适呢?(步子跨大了,容易扯着蛋)

设n为有序数组中元素的总个数,m为跳跃步长,那么跳跃次数为n/m。最坏的情况是,数组中倒数第二个元素为我们要查找的元素,线性查找的比较次数是m-1。这个算法在最坏情况的比较次数为(n/m + (m-1))。

现在就变成了数学问题:求m、n为何值时(n/m + (m-1))的值最小。

计算结果:当m=sqrt(n)时,n/m+(m-1)的值最小,也就是我们应该把步长设置为√n(n的平方根)。

C语言实现:

跳跃查找要点:

  • 只适用于有序数组
  • 跳跃查找算法时间复杂度为O(√n),处于线性查找O(n)和二分查找O(log n)之间
  • 什么时候使用跳跃查找?二分查找通常比跳跃查找要好,但是跳跃查找只需往回跳一次,而二分查找在最坏情况下需跳O(log n)次。如果往回跳代价比较高,可以选择使用跳跃查找。

发表评论

电子邮件地址不会被公开。 必填项已用*标注