数据结构——有序向量的查找与改进
2022/1/30 6:06:03
本文主要是介绍数据结构——有序向量的查找与改进,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
有序向量的查找
查找
- 接口:tempalte
static Rank search(T* a,T const& e, Rank lo, Rank hi) - 语义规定:在有序向量的区间[lo, hi)内,确定不大于e的最后一个节点的秩
- 复杂度:若采用最朴素的二分策略,那么每次都将问题规模缩小一半左右,这样经过至多\(log_2(hi-lo)\)次迭代,复杂度不超过\(O(logn)\),而改进基本上是线性因子。
- 查找长度:查找算法执行元素大小比较操作的次数
二分查找
语义规定:在有序向量的区间[lo, hi)内,返回e的秩,若有多个相同值则返回最大的秩,若查询失败则返回-1
原理:每次取lo与hi的终点,不停调整区间,经过至多两次比较可以完成一次迭代。
直到最后lo>=hi时(其实就是lo=hi),此时的区间宽度为0,表示查询失败了。
// 二分查找算法(版本A):在有序向量的区间[lo, hi)内查找元素e,0 <= lo <= hi <= _size template <typename T> static Rank binSearch ( T* S, T const& e, Rank lo, Rank hi ) { while ( lo < hi ) { //每步迭代可能要做两次比较判断,有三个分支 Rank mi = ( lo + hi ) >> 1; //以中点为轴点(区间宽度的折半,等效于宽度之数值表示的右移) if ( e < S[mi] ) hi = mi; //深入前半段[lo, mi)继续查找 else if ( S[mi] < e ) lo = mi + 1; //深入后半段(mi, hi)继续查找 else return mi; //在mi处命中 } //成功查找可以提前终止 return -1; //查找失败 } //有多个命中元素时,不能保证返回秩最大者;查找失败时,简单地返回-1,而不能指示失败的位置
查询长度分析:
为了评定各个查询的细微差距,我们考察查询长度,同样有最好最坏和平均。
这里我们依旧考察平均查询长度:\(C_{average}(k)\)
设在长度为\(n=2^k-1\)的有序向量中进行查询
1、成功查询长度
递推基:
\(C_{average}(k)=C(1)=2\)
递推分析:对于成功查询,总共有三种情况
1.经过1次比较,问题转化为2^{k-1}-1的新问题;
2.经过2次比较,问题转化为2^{k-1}-1的新问题;
3.经过2次比较,在mid处命中,查询成功.
那么则有递推公式
令
\[F(k)=C(k)-3k*2^{k-1}-1 \]则有
\[F(1)=2;F(k)=2F(k-1)=2^2F(k-2)=\dots=2^{k-1}F(1)=-2^k \]于是
\[C(k) = F(k)+3k*2^{k-1}+1=(\frac{3}{2}k-1)*(2^k-1)+ \frac{3}{2}k \]进而得到
\[C_{average}=\frac{C(k)}{2^k-1}=\frac{3}{2}k-1+\frac{3}{2}k*\frac{1}{2^k-1}=\frac{3}{2}k-1+O(\varepsilon) \]n趋于无穷时忽略末尾收敛的无穷小量平均查找长度为:
\[O(1.5k)=O(1.5\cdot log_{2}n) \]Fibonacci查找
二分查找·改
// 二分查找算法(版本B):在有序向量的区间[lo, hi)内查找元素e,0 <= lo < hi <= _size template <typename T> static Rank binSearch ( T* S, T const& e, Rank lo, Rank hi ) { while ( 1 < hi - lo ) { //每步迭代仅需做一次比较判断,有两个分支;成功查找不能提前终止 Rank mi = ( lo + hi ) >> 1; //以中点为轴点(区间宽度的折半,等效于宽度之数值表示的右移) ( e < S[mi] ) ? hi = mi : lo = mi; //经比较后确定深入[lo, mi)或[mi, hi) } //出口时hi = lo + 1,查找区间仅含一个元素A[lo] return e < S[lo] ? lo - 1 : lo; //返回位置,总是不超过e的最大者 } //有多个命中元素时,返回秩最大者;查找失败时,简单地返回-1,而不能指示失败的位置
二分查找·改二
template <typename T> static Rank binSearch ( T* S, T const& e, Rank lo, Rank hi ) { while ( lo < hi ) { //每步迭代仅需做一次比较判断,有两个分支 Rank mi = ( lo + hi ) >> 1; //以中点为轴点(区间宽度的折半,等效于宽度之数值表示的右移) ( e < S[mi] ) ? hi = mi : lo = mi + 1; //经比较后确定深入[lo, mi)或(mi, hi) } //成功查找不能提前终止 return lo - 1; //循环结束时,lo为大于e的元素的最小秩,故lo - 1即不大于e的元素的最大秩 } //有多个命中元素时,返回秩最大者;查找失败时,能够返回失败的位置
这篇关于数据结构——有序向量的查找与改进的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-09-28微服务架构中API版本控制的实践
- 2024-09-28AI给的和自己写的Python代码,都无法改变输入框的内容,替换也不行
- 2024-09-27Sentinel配置限流资料:新手入门教程
- 2024-09-27Sentinel配置限流资料详解
- 2024-09-27Sentinel限流资料:新手入门教程
- 2024-09-26Sentinel限流资料入门详解
- 2024-09-26Springboot框架资料:初学者入门教程
- 2024-09-26Springboot框架资料详解:新手入门教程
- 2024-09-26Springboot企业级开发资料:新手入门指南
- 2024-09-26SpringBoot企业级开发资料新手指南