设为“置顶或星标”，第一时间送达干货。
转自景禹
今天我们一起来看三款经典的排序算法！
跳跃查找（Jump Search）
与二分查找类似，跳跃查找也是在有序数组上进行的。基本思想是以固定步长向前跳越，从而跳过尽可能多的不在待查找元素附近的元素，减少查找过程中的比较次数。
比如，假设我们有一个大小为 n 的数组 arr[] 和一个步长 m，那么我们仅查找 arr[0],arr[m],arr[2m],…,arr[km] 等等位置。当发现了待查找元素 x 位于区间 , 则在该区间上进行线性查找（Linear Search ） ，继而确定待查找元素是否存在，若存在返回待查找元素 x 的下标；若不存在，则返回 -1。
为了清楚起见，景禹以下面的例子带大家一起 Step By Step。
数组的长度为16，假定我们取步长为 ，我们以查找元素88为例进行说明。跳跃查找，总体可以分为两步：第一步确定待查找元素的范围，第二步线性搜索第一步确定的范围。
如何确定待查找元素的范围？
我们设置一个保存待查找范围左区间的指针pre，还有一个进行扫描的指针 step，每次按照步长 4 向前跳跃，具体我们一步一步看一下。
第一步：变量pre 指向下标为0的位置，step 指向数组中下标为4的位置。
第二步：判断 step 指向的元素的前一个元素 21 与待查找元素88的大小，若小于待查找元素，则移动pre指针到step的位置，并将step更新为step加上步长；否则，线性查找 pre指针到 step 指针范围。这里21小于88，则将 pre 更新为4，将step更新为8。
第三步：判断 step指向的元素的前一个元素 75 与 88 的大小，发现小于88，则将 pre 更新为step的值 8，将step的值更新为 step + 步长，即 8+4=12.
第四步：判断 step指向的元素的前一个元素 101 与 88 的大小，发现大于88，故可以确定88在 的范围之内。具体88是否存在，则可以通过线性查找区间 即可。
第五步：线性查找区间 ，判断pre指向的元素80与88的大小，发现小于，则将pre指针向前移动到下标9.
第六步：判断pre指向的元素88与待查找元素相等，则返回下标 9 。
实现代码
public class JumpSearch
{
public static int jumpSearch(int[] arr, int x)
{
int n = arr.length;
//将step初始化为步长（根号下数组长度）
int step = (int)Math.floor(Math.sqrt(n));
//将prev初始化为0
int prev = 0;
//确定待查找元素所在范围
while (arr[Math.min(step, n)-1] < x)
{
prev = step;
step += (int)Math.floor(Math.sqrt(n));
if (prev >= n)
return -1;
}
//从pre==8开始线性查找元素88
while (arr[prev] < x)
{
prev++;
//如果到达了step或者数组的末尾都没找到，则返回-1.
if (prev == Math.min(step, n))
return -1;
}
//如果相等则找到了待查找元素。
if (arr[prev] == x)
return prev;
return -1;
}
public static void main(String [ ] args)
{
int arr[] = { 5, 13, 19, 21, 37, 56, 64, 75, 80,
88, 92, 101, 156, 218, 315, 458};
int x = 88;
int index = jumpSearch(arr, x);
System.out.println("nNumber " + x +
" is at index " + index);
}
}
时间复杂度分析
对于一个包含n的元素的有序数组，最坏的情况下，需要进行 次跳跃且最后一个元素的值大于待查找元素，则还需要进行线性查找，进行m-1比较。因此，跳跃查找最坏情况下执行 次，当 时， 取得最小值，也就意味着时间复杂度最低，最好的步长为 。跳跃查找的时间复杂度则为 量级。
跳跃查找小结
跳跃查找与二分查找一样都是在有序数组上进行的；
跳跃查找的最佳步长 。
跳跃的时间复杂度 介于线性查找的时间复杂度 和二分查找 之间。
二分查找比跳跃查找的时间复杂度更低，但是跳跃查找的优势在于仅需要回溯一次（即线性遍历的部分），而在搜索数组中最小的元素或者最大元素的情况下，二分查找需要回溯多次。因此，在二分查找成本很高的时候，我们可以考虑跳跃查找。
插值查找(Interpolation Search)
给定一个包含 n 个元素且 均匀分布 的有序数组 arr[]，查找该数组中的某个特定元素 x 就可以考虑插值查找。线性查找（Linear Search）时间复杂度为 ，跳跃查找（Jump Search）为 ，二分查找为 .
对于一个 均匀分布 的有序数组而言， 插值查找是对于二分查找的改进。二分查找总是对于一个查找区间的中间值进行检查，而插值查找则没有这个局限性，插值查找根据要查找的值确定查找的位置，比如查找靠近有序数组最末尾的元素时，插值查找倾向于直接从有序数组的末端进行查找，而不会像二分查找，每一次都查找查找区间内的中间元素，然后不断缩减查找区间，直到靠近有序数组的末尾。
二分查找中求 mid 索引的公式为：
插值查找求 mid 索引的公式为：
至于这个计算公式的有效性证明景禹就不装大尾巴了，感兴趣的小禹禹可以后台回复 “插值查找” 获取论文下载链接，自行研究。小禹禹对这个公式也可以简单理解为，当查找的元素靠近 arr[high] 时，这个公式计算出来的 mid 也靠近 high；当查找的元素靠近 arr[low] 时，公式计算出的 mid 就靠近 low 。
那我们以下面的例子一起愉快地开始学习算法本身的执行过程吧。我们以查找元素18为例进行说明。
第一步：计算mid，low 等于0，high等于14，arr[low]为10，arr[14]为47， .
第二步：将mid指向的元素16与待查找元素18比较，发现小于18，则将low更新为mid+1，即为4的位置。这一步骤和二分查找是一样的。
第三步，重新计算mid，. 则mid指向下标为4的位置。
第四步：比较mid指向的元素18和查找元素18，发现相等，则返回mid的值4。
实现代码
与二分查找类似，只需要将mid的计算方法进行更改，再加一些细节上的判断。同样，景禹给大家提供递归和迭代两种实现方式。
插值查找迭代实现
class Test
{
//定义测试数据
static int arr[] = new int[]{10, 12, 13, 16, 18, 19, 20, 21, 22, 23,
24, 33, 35, 42, 47};
//插值查找迭代实现
static int interpolationSearch(int x)
{
// 分别设置 low 和 high 的初始值。
int low = 0, high = (arr.length - 1);
//low <= high指针，且查找元素x 在 arr[low] 与 arr[high]的范围内。
while (low <= high && x >= arr[low] && x <= arr[high])
{
//当low 与 high 相遇时，判断当前low指向的值是否与查找元素x相等
//相等返回low或者high；否则返回-1.
if (low == high)
{
if (arr[low] == x) return low;
return -1;
}
//计算mid的值
int mid = low + (((high-low) /
(arr[high]-arr[low]))*(x - arr[low]));
//判断mid指向的值是否和查找元素x相同
if (arr[mid] == x)
return mid;
//如果mid指向的值小于 x，则将low 更新为mid+1
//否则，即mid指向的值大于x，则将high更新为mid-1
if (arr[mid] < x)
low = mid + 1;
else
high = mid - 1;
}
return -1;
}
public static void main(String[] args)
{
int x = 18; // Element to be searched
int index = interpolationSearch(x);
// If element was found
if (index != -1)
System.out.println("Element found at index " + index);
else
System.out.println("Element not found.");
}
}
插值查找递归实现
#include <stdio.h>
//插值查找递归实现
int interpolationSearch(int arr[], int low, int high, int x)
{
int mid;
if( low <= high && x >= arr[low] && x <= arr[high])
{
mid = low + ( ( (double)( high - low ) /
( arr[high] - arr[low] ) ) * ( x - arr[low] ) );
if( arr[mid] == x )
return mid;
if( arr[mid] < x )
return interpolationSearch( arr, mid+1, high, x);
if( arr[mid] > x )
return interpolationSearch( arr, low, mid-1, x);
}
return -1;
}
int main()
{
int arr[] = {10, 12, 13, 16, 18, 19, 20, 21, 22, 23,
24, 33, 35, 42, 47};
int n = sizeof(arr)/sizeof(arr[0]);
int x = 18;
int index = interpolationSearch(arr, 0, n-1, x);
if (index != -1)
printf("Element found at index %d", index);
else
printf("Element not found.");
return 0;
}
时间复杂度
插值查找的平均时间复杂度为 ，证明过程不像前面的跳跃查找简单的一阶导数就可以求出来。对于插值查找感兴趣的小禹禹，可以后台回复 「插值查找」获取原始论文下载链接。
当数组不是 均匀分布 的有序数组，那么插值查找的时间复杂度会退化为 。举一个极端的例子，比如数组arr[] = { 1, 10，100，1000}，我们查找元素 100。第一次计算出的索引为 0，第二次计算的索引值为1，第三次索引值为2，此时找到了查找元素，但是这就和线性查找一个样，相当于一次遍历整个数组，所以时间复杂度最坏情况下为 级别。
斐波那契查找
斐波那契查找，又称为黄金分割比查找，同样是二分查找的变种。黄金分割 0.618，这个数字相信小禹禹再熟悉不过了，而斐波那契数列就是黄金分割的典型例证。
下面景禹带小禹禹一起学习一下斐波那契数列到底是如何对二分查找进行优化的？
斐波那契数列如下所示：
除第一个和第二个元素之外，其他元素都等于其前面两个的元素之和。
小禹禹：那这个数列和黄金分割有啥子关系奥？
景禹：除第一个元素与第二个元素比值为1，后面的元素前一个比后一个的比值随着斐波那契数越大，比值越接近0.618，比如，1/2=0.5，8/13=0.615，而233/377=0.618，这就是为什么又把这个查找算法叫做黄金分割的原因。
斐波那契查找与插值查找都是对 mid 的选择方式进行的改进，看下图，相信你一定看懂斐波那契查找，mid的选取策略。
斐波那契的递推公式为： 。如上图所示，假设数组包含12个元素，第一次，我们则整个数据分割成 13 – 1 = （5-1）+（8-1）+1， 即[low，mid-1]包含的4个元素、mid 本身、以及[mid+1, high]包含的7个元素，mid则对应于下标为4的元素。具体斐波那契查找是如何执行的，我们以一个完整的例子进行Step By Step.
对于上面包含11个元素的数组，假设我们查找元素80。
第一步：寻找一个大于或等于数组长度 11 的最小斐波那契数 13，我们令FibM = 13，并分别将FibM前面的两个斐波那契数保存在 FibMm2 = 5、FibMm1 = 8，即 ， ， 。那么就会将数组分割成 , 。设置一个offset值，初始化为-1，.
第二步：将mid指向的元素37 与待查找元素80进行比较，发现小于80，则将 FibM = FibMm1 = 8，将FibMm1 = FibMm2 = 5, 将 FibMm2 = FibM – FibMm1 = 8- 5 = 3，offset = mid = 4 。此时 mid 将更新为 offset + FibMm2 = 4 + 3 = 7.
第三步：将mid指向的元素75与待查找元素80进行比较，发现小于80，则将FibM = FibMm1 = 5，将FibMm1 = FibMm2 = 3，将FibMm2 = FibM – FibMm1 = 5 – 3 = 2 ，offset = mid = 7。此时mid = offset + FibMm2 = 7 + 2 = 9.
第四步：将mid指向的元素88与待查找元素80进行比较，发现大于80，则将FibM = FibMm2 = 2，将FibMm2 = FibMm1 – FibMm2 = 1，FibMm1 = FibM -FibMm1 = 2 -1 = 1，offset = 7，不更新。mid 将更新为 offset + FibMm2 = 8
第五步：将mid指向的元素80与待查找元素相同，则返回mid，即返回8.
到这里，我想小禹禹一定理解了一大半了，但难免还有一点儿疑惑，比如offset是干嘛的，以及offset何时被更新，什么时候又不更新，那就到下面的代码里找答案吧， 一定要留意注释奥！
斐波那契查找的实现
/*斐波那契查找*/
int fibMonaccianSearch(int arr[], int x, int n)
{
//初始化斐波那契数列
int fibMm2 = 0; // 第(m-2)个斐波那契数
int fibMm1 = 1; // 第(m-1)个斐波那契数
int fibM = fibMm2 + fibMm1; //第m个斐波那契数。
/* fibM 保存大于等于数组长度 n 的最小斐波那契数*/
while (fibM < n)
{
fibMm2 = fibMm1;
fibMm1 = fibM;
fibM = fibMm2 + fibMm1;
}
// 用于标记已经查找过且不需要再查找的数组的下标
//初始化为-1
int offset = -1;
/* 斐波那契查找函数主体；注意：我们将arr[offset+fibMm2] 与 x
进行比较，当FibM 等于1的时候，FibMm2 变为0
FibM = 13 */
while (fibM > 1)
{
// 确保mid 在数组的下标范围之内
int mid = min(offset+fibMm2, n-1); // mid = 4 7 9 8
/*如果mid指向的元素小于查找元素 x
则说明mid之前的元素都不需要再查找了，将offset更新为mid*/
if (arr[mid] < x)
{
fibM = fibMm1; //8 5
fibMm1 = fibMm2; //5 3
fibMm2 = fibM - fibMm1; //3 2
offset = mid; //4 7
}
/*如果mid指向的元素大于x，仅更新斐波那契数，offset不需要
因为待查找数可能就在offset到mid之前，更新了就查不到了*/
else if (arr[mid] > x)
{
fibM = fibMm2; 2
fibMm1 = fibMm1 - fibMm2; 1
fibMm2 = fibM - fibMm1; 1
}
/* 相等则返回mid*/
else return mid;
}
/* 将 x 与数组的最后一个元素进行比较 */
if(fibMm1 && arr[offset+1]==x)return offset+1;
return -1;
}
时间复杂度
斐波那契查找的最坏和平均时间复杂度都为 . 具体的证明感兴趣的小禹禹可以后台回复 「查找算法」获取论文下载链接。
斐波那契查找与二分查找比较
相同点：
-
都是在有序数组上进行的（所有的区间查找算法都是在有序数组上进行的） -
同属于分治思想的应用（二分与斐波那契查找都是将问题域不断地缩小，直到查找成功或者失败，缩减搜索空间你也可以理解成贪心的方法） -
时间复杂度都为 .
不同点
-
斐波那契查找将给定数组分割成大小不相等的两部分，黄金分割。 -
二分查找使用除法操作进行范围的划分；斐波那契则不需要使用除法，而是使用加减，除法操作在CPU的消耗上可能代价更大。 -
斐波那契查找在后续步骤当中检查相对较近的元素。因此，当输入的数组很大而无法容纳在CPU的Cache中，甚至RAM中也无法容纳时，斐波那契查找将很有用。
总结
今天景禹给小禹禹介绍了3个查找算法：跳跃查找（Jump Search）、插值查找（Interpolation Search）和斐波那契查找（Fibonacci Search），这三种查找方法与二分查找类似，都属于区间查找方法，每种方法各有有缺，在实际应用中根据数据特征还有硬件等进行恰当调整即可。
推荐阅读
• C++是如何从代码到游戏的？• 告诉你一个学习编程的诀窍（建议收藏）• 自学编程的八大误区！克服它！• 新手如何有效的刷算法题（LeetCode）• 10款VS Code插件神器，第7款超级实用！• 在拼多多上班，是一种什么样的体验？我tm心态崩了呀！• 写给小白，从零开始拥有一个酷炫上线的网站！
欢迎关注我的公众号“五分钟学算法”，如果喜欢，麻烦点一下“在看”~
原文始发于微信公众号（五分钟学算法）：图解：三款经典的查找算法，等着你
