跳转搜索

像 二叉查找,跳转搜索 (要么区块搜索) 是排序数组的搜索算法. 基本思想是通过固定步骤向前跳跃 或 跳过一些元素 来代替 搜索所有元素 来检查更少的元素 (比起 线性搜索) .

例如,假设我们有一个数组arr[],大小n,并 (跳跃) 大小m的块. 然后我们搜索 索引arr[0],arr[m],arr[2 * m],...,arr[k * m]等等. 一旦找到arr[k * m] < x < arr[(k+1) * m]数组块,我们从索引k * m执行线性搜索 操作找到元素x.

要跳过的最佳块大小 m 是多少? 在最坏的情况下,我们必须做n/m次跳转,如果最后检查的值大于要搜索的元素,那么我们就执行了m - 1次比较的线性搜索. 因此,最坏情况下的比较总数将是((n/m) + m - 1). 而((n/m) + m - 1)方程的最小值,是当m = √n时. 因此,最佳步长是m = √n.

复杂性

时间复杂: O(√n)- 因为我们按√n大小块搜索.

参考

• GeeksForGeeks
• Wikipedia