查找算法
作者:
sorry510 | 来源:发表于
2020-03-04 17:00 被阅读0次
- 顺序查找 时间复杂度O(n)
- 折半查找（二分查找） 时间复杂度O(logn) 把n个数化为一颗二叉树输的高度为logn
- 差值查找 将分割值mid改为
low+(high-low)*(key-a[low])/(a[high]-a[low]),a为查找的序列
例如:
a = [1, 16, 24, 35, 47, 59, 62, 73, 88, 99], low=0，high=9，a[low]=1,a[high]=99，key为要找的数
- 斐波那契查找（黄金分割原理），按照斐波那契序列分割序列
F=[1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89]
a为需要查找的序列，需要的F序列为F[k]-1 >= len(a)的k最小值,关键算法为
mid = low + F[k-1] - 1;
if(key < a[mid]) {
high = mid - 1;
k -= 1;
}else if(key > a[mid]) {
low = mid + 1;
k -= 2;
}else {
return mid;
}
本文标题：查找算法
本文链接：https://www.haomeiwen.com/subject/cnxwchtx.html
网友评论