四大查找算法
在Java中，常用的查找算法有以下四种：
- 顺序查找；
- 二分查找；
- 插值查找；
- 斐波那契查找；
欢迎大家关注我的公众号 javawebkf，目前正在慢慢地将简书文章搬到公众号，以后简书和公众号文章将同步更新，且简书上的付费文章在公众号上将免费。
一、顺序查找
顺序查找非常简单，就是遍历数组，找到了就返回元素下标，代码如下：
public static int find(int[] arr, int targetNum){
if (arr == null) {
return -1;
}
for (int i = 0; i < arr.length; i++) {
if (arr[i] == targetNum){
return i;
}
}
return -1;
}二、二分查找
二分查找又叫折半查找，首先二分查找的数列是要有序的，如果无序就不能用二分查找。
1. 二分查找思路：
- 首先确定该数组的中间下标，`mid = (left + right) / 2；
- 然后让
arr[mid]和要和查找的元素比较，如果要查找的元素更大，说明应该向右查找，反之向左； - 将左(右)边当成一个新数组，重复第一第二步，即进行递归。找到了就结束递归，或者遍历完了数组也没找到也结束递归。
2. 代码实现：
public static int find(int[] arr, int left, int right, int targetNum){
if (left > right){
return -1;
}
int mid = (left + right) / 2;
if (arr[mid] > targetNum) {
return find(arr, left, mid - 1, targetNum);
} else if (arr[mid] < targetNum){
return find(arr, mid + 1, right, targetNum);
} else {
return mid;
}
}三、插值查找
插值查找也是二分查找，不同的是，mid的计算公式不再是mid = (left + right) / 2，变成了mid = left + (targetNum- arr[left]) / (arr[right] - arr[left]) * (right -left)，其他的都和二分查找一样。这个mid的计算公式是大佬发明的，大家有兴趣可以用数学推导一下。
四、斐波那契查找
斐波那契查找又叫黄金分割查找，黄金分割是初中学习的内容，之后又学习了斐波那契数列。
1, 1, 2, 3, 5, 8, 13……这个就是斐波那契数列，相邻两个数的比值无限接近黄金分割值0.618。斐波那契查找就是利用斐波那契数列的这个特性来设计的查找算法。
1. 斐波那契查找介绍：
斐波那契查找和二分查找、插值查找也类似，数组也要是有序的。不同之处还是mid的计算方法。公式为：mid = left + f(k-1) - 1。对于这个公式做几点说明：
- 斐波那契数列是符合
f(k) = f(k-1) + f(k-2)的一个数列，例如1, 1, 2, 3, 5, 8……； - 要使用斐波那契查找，就要先构建一个斐波那契数列，用来获取中间索引
mid； - 斐波那契数列的长度就和原始数组保持一致即可；
left表示原始数组左边索引，初始的时候就是0，构建好斐波那契数组，我们要让f(k-1) - 1指向数组的最后一个索引；- 然后从斐波那契数组中根据
mid = left + f(k-1) - 1来获取中间索引； - 然后创建一个新数组，长度为
f(k)，因为长度为f(k)的数组才满足f(k) = f(k-1) + f(k-2)，才能使用斐波那契数列去获取mid索引。将原始数组的所有数拷贝过去，如果f(k)的值大于原始数组的长度，那就就将超出长度的部分用原始数组的最后一个数填充； - 根据
mid索引去上面创建的新数组中获取元素进行比较； - 如果这个数比要查找的数更小，那说明在原始数组的
mid的左边，那就让right = mid - 1，同时k要减1，因为刚才我们是在斐波那契数列f(k)的位置获取的索引，在f(k)的前面，有f(k-1)个元素，将这个f(k-1)个元素继续拆分，就可以拆成f(k-1) = f(k-2) + f(k-3)，再根据mid = left + f(k-1-1) - 1重新获取mid； - 如果这个数比要查找的数更大，就让
left = mid + 1，同时k要减2，因为上面说了，斐波那契数列满足f(k) = f(k-1) + f(k-2)，在f(k)的左边，有f(k-1)个元素，右边有f(k-2)个元素，继续拆分就变成了f(k-2) = f(k-3) + f(k-4)，所以是k-2，再根据mid = left + f(k-1-2) - 1重新获取mid； - 如果
mid对应是数刚好等于被查找数，那说明找到了，mid索引就是就被查找元素的位置，但是不能直接返回mid，因为上面说了，f(k)可能比原始数组长度更长，超出部分用原始数组最后一个元素填充，如果直接返回mid，此时mid可能指向的是超出部分的元素，用这个mid去原始数组中找，就越界了，所以应该返回mid和right中较小的那个。
2. 代码实现：
public static int find(int[] arr, int targetNum){
int left = 0; // 原始数组最左边的下标
int right = arr.length - 1; // 原始数组最右边的下标
int k = 0; // 表示斐波那契分割数值的下标
int mid = 0; // 初始化mid为0
// 获取到斐波那契数列
int[] f = fib(arr.length);
// 让f(k) - 1指向数组的最后一个索引
while (f[k] - 1 < right){
k++;
}
// 但是f(k)不是步长为1的递增数列，所以可能出现 f(k) - 1 的值大于原始数组最后一个索引的情况
// 比如原始数组最大索引为4，那么此时f(k)就等于5，所以需要构造一个新数组，长度不够的部分会用0填充
int[] temp = Arrays.copyOf(arr, f[k]);
// 将Arrays.copyof()方法填充的0用原始数组最后一个数填充
for (int i = right + 1; i < temp.length; i++) {
temp[i] = arr[right];
}
// 循环查找targetNum
while (left <= right){
mid = left + f[k-1] - 1;
if (targetNum < temp[mid]){ // 向左查找
right = mid - 1;
k--;
} else if (targetNum > temp[mid]){ // 向右查找
left = mid + 1;
k -= 2;
} else { // 返回mid和right中较小的值
return mid <= right ? mid : right;
}
}
return -1;
}
/**
* 得到一个斐波那契数列
* @return
*/
public static int[] fib(int length){
int[] fibArr = new int[length];
fibArr[0] = 1;
fibArr[1] = 1;
for (int i = 2; i < length; i++) {
fibArr[i] = fibArr[i-1] + fibArr[i-2];
}
return fibArr;
}本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录