数据结构与算法系列 (5) 查找算法
2020-03-08 本文已影响0人
suxin1932
1.概述
常用的查找有四种:
1) 顺序(线性)查找
2) 二分查找/折半查找
3) 插值查找
4) 斐波那契(黄金分割法)查找
2.常见的查找算法
2.1 顺序(线性)查找
2.1.2 代码示例
@Test
public void fn01() {
int[] arr = {12, -3, 5, 102, 20, 7};
System.out.println(sequenceSearch(arr, 6));
}
/**
* 查找算法一: 线性查找, 即遍历数组即可 (注意: 这里只返回一个)
*
* @param arr
* @param v
* @return
*/
public static int sequenceSearch(int[] arr, int v) {
for (int i = 0; i < arr.length; i++) {
if (v == arr[i]) {
return i;
}
}
return -1;
}
2.2 二分查找/折半查找
前提是数组必须是有序的(从大到小或从小到大排列).
如果不符合, 可以先对数组排序后, 再进行二分查找.
2.2.2 代码示例
@Test
public void fn02() {
// int[] arr = {1, 2, 3, 4, 5, 6, 7, 8};
int[] arr = {8, 7, 6, 4, 3, 2, 1};
System.out.println(binarySearch(arr, 5, 0, arr.length - 1));
}
/**
* 查找算法二: 二分查找, 要求数组必须是有序的, 这里如果有多个目标值也是只返回了一个下标
* @param arr
* @param v
* @param start
* @param end
* @return
*/
public static int binarySearch(int[] arr, int v, int start, int end) {
if (v == arr[start]) {
return start;
}
if (v == arr[end]) {
return end;
}
if (start > end) {
return -1;
}
int mid = (start + end) >> 1;
if (v > arr[start] && v < arr[end]) {
if (v == arr[mid]) {
return mid;
} else if (v > arr[mid]) {
start = mid + 1;
} else {
end = mid - 1;
}
return binarySearch(arr, v, start, end);
} else if (v < arr[start] && v > arr[end]) {
if (v == arr[mid]) {
return mid;
} else if (v > arr[mid]) {
end = mid - 1;
} else {
start = mid + 1;
}
return binarySearch(arr, v, start, end);
} else {
return -1;
}
}
2.3 插值查找
#插值查找(与二分查找类似, 区别是 mid 值的计算不同)
要求数组必须是有序的, 核心是 mid 值的计算:
int mid = left + (right – left) * (findVal – arr[left]) / (arr[right] – arr[left])
#插值查找注意事项
>> 对于数据量较大，关键字分布比较均匀的查找表来说，采用插值查找, 速度较快.
>> 关键字分布不均匀的情况下，该方法不一定比折半查找要好
2.3.2 代码示例
@Test
public void fn03() {
// int[] arr = {1, 2, 3, 4, 5, 6, 7, 8};
int[] arr = {8, 7, 6, 4, 3, 2, 1};
System.out.println(insertSearch(arr, 3, 0, arr.length - 1));
}
/**
* 查找算法三: 插值查找, 要求数组必须是有序的, 这里如果有多个目标值也是只返回了一个下标
* int mid = left + (right – left) * (findVal – arr[left]) / (arr[right] – arr[left])
* @param arr
* @param v
* @param start
* @param end
* @return
*/
public static int insertSearch(int[] arr, int v, int start, int end) {
if (v == arr[start]) {
return start;
}
if (v == arr[end]) {
return end;
}
if (start >= end) {
return -1;
}
int mid = start + (end - start) * (v - arr[start]) / (arr[end] - arr[start]);
if (v > arr[start] && v < arr[end]) {
if (v == arr[mid]) {
return mid;
} else if (v > arr[mid]) {
start = mid + 1;
} else {
end = mid - 1;
}
return insertSearch(arr, v, start, end);
} else if (v < arr[start] && v > arr[end]) {
if (v == arr[mid]) {
return mid;
} else if (v > arr[mid]) {
end = mid - 1;
} else {
start = mid + 1;
}
return insertSearch(arr, v, start, end);
} else {
return -1;
}
}
2.4 斐波那契(黄金分割法)查找
2.4.1 概念
#斐波那契数列(黄金分割数列)
指的是这样一个数列：1、1、2、3、5、8、13、21、····，在数学上，斐波那契被递归方法如下定义：
F(1)=1，F(2)=1，F(n)=f(n-1)+F(n-2) （n>=2）。
该数列越往后相邻的两个数的比值越趋向于黄金比例值（0.618）。
#斐波那契查找
就是在二分查找的基础上根据斐波那契数列进行分割的。
在斐波那契数列找一个等于略大于查找表中元素个数的数F[n]，
将原查找表扩展为长度为F[n](如果要补充元素，则补充重复最后一个元素，
直到满足F[n]个元素)，完成后进行斐波那契分割，
即F[n]个元素分割为前半部分F[n-1]个元素，后半部分F[n-2]个元素，
找出要查找的元素在那一部分并递归，直到找到。
斐波那契查找的时间复杂度还是O(log 2 n )，但是 与折半查找相比，
斐波那契查找的优点是它只涉及加法和减法运算，而不用除法，而除法比加减法要占用更多的时间，
因此，斐波那契查找的运行时间理论上比折半查找小，但是还是得视具体情况而定。
对于斐波那契数列：1、1、2、3、5、8、13、21、34、55、89……（也可以从0开始），
前后两个数字的比值随着数列的增加，越来越接近黄金比值0.618。
比如这里的89，把它想象成整个有序表的元素个数，
而89是由前面的两个斐波那契数34和55相加之后的和，
也就是说把元素个数为89的有序表分成由前55个数据元素组成的前半段和由后34个数据元素组成的后半段，
那么前半段元素个数和整个有序表长度的比值就接近黄金比值0.618，
假如要查找的元素在前半段，那么继续按照斐波那契数列来看，55 = 34 + 21，
所以继续把前半段分成前34个数据元素的前半段和后21个元素的后半段，
继续查找，如此反复，直到查找成功或失败，这样就把斐波那契数列应用到查找算法中了。
斐波那契数列：1、1、2、3、5、8、13、21、34、55、89…….png
从图中可以看出，当有序表的元素个数不是斐波那契数列中的某个数字时，
需要把有序表的元素个数长度补齐，让它成为斐波那契数列中的一个数值，
当然把原有序表截断肯定是不可能的，不然还怎么查找。
然后图中标识每次取斐波那契数列中的某个值时(F[k])，都会进行-1操作，
这是因为有序表数组位序从0开始的，纯粹是为了迎合位序从0开始。
2.4.2 代码实现
@Test
public void fn04() {
int[] arr = {1,2,3,4,5,6,7,8};
System.out.println(fibonacciSearch(arr, -1, 10));
}
private static int[] fibonacci(int max) {
int[] arr = new int[max];
int i = 0;
arr[0] = 1;
arr[1] = 1;
for (i = 2; i < max; i ++) {
arr[i] = arr[i - 1] + arr[i - 2];
}
return arr;
}
public static int fibonacciSearch(int[] arr, int v, int max) {
int low = 0;
int high = arr.length - 1;
int mid = 0;
// 斐波那契分割数值下标
int k = 0;
// 序列元素个数
int i = 0;
// 获取斐波那契数列
int[] fibonacciArr = fibonacci(max);
// 获取斐波那契分割值下标
while (arr.length > fibonacciArr[k] - 1) {
k++;
}
// 创建临时数组
int[] tmp = new int[fibonacciArr[k] - 1];
System.arraycopy(arr, 0, tmp, 0, arr.length);
// 序列补充至 fibonacciArr[k] 个元素
for (i = arr.length; i < fibonacciArr[k] - 1; i++) {
tmp[i] = tmp[high];
}
while (low <= high) {
// low：起始位置
// 前半部分有f[k-1]个元素，由于下标从0开始
// 则-1 获取 黄金分割位置元素的下标
mid = low + fibonacciArr[k - 1] - 1;
if (tmp[mid] > v) {
// 查找前半部分，高位指针移动
high = mid - 1;
// （全部元素） = （前半部分）+（后半部分）
// f[k] = f[k-1] + f[k-1]
// 因为前半部分有f[k-1]个元素，所以 k = k-1
k -= 1;
} else if (tmp[mid] < v) {
// 查找后半部分，低位指针移动
low = mid + 1;
// （全部元素） = （前半部分）+（后半部分）
// f[k] = f[k-1] + f[k-1]
// 因为后半部分有f[k-1]个元素，所以 k = k-2
k -= 2;
} else {
if (mid <= high) {
// 如果为真则找到相应的位置
return mid;
} else {
// 出现这种情况是查找到补充的元素
// 而补充的元素与high位置的元素一样
return high;
}
}
}
return -1;
}
参考资料
https://blog.csdn.net/jinyan1111/article/details/79916455 (斐波那契查找)
