首页 / 算法 / 算法 在连续线性空间里查找
算法 在连续线性空间里查找
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了算法 在连续线性空间里查找，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2314字，纯文字阅读大概需要4分钟。
内容图文
算法 在连续线性空间里查找
查找可以分成：有序和无序查找
无序查找
顺序比较
缺点：效率低下
//e为查找的对象，lo和hi是要查找的区间
template <typename T>
Rank Vector<T>::find(T const & e, Rank lo, Rank hi){
while(hi != lo && _elem[hi-1] != e){
hi--;
}
return hi - 1;
}有序查找
原理：找个某个点，根据这个点切分成2个区间。
1，二分查找（binary search）
这个点是：中间点
- 优点：简单，最坏情况的效率也不低
- 缺点：如果要查找的值在中间点的右侧就比在左侧多一次比较
//二分查找算法：在有序向量的区间[lo, hi)内查找元素e，0 <= lo <= hi <= _size
template<typename T>
Rank Vector<T>::search ( T const& e, Rank lo, Rank hi ) const {
while ( lo < hi ) { //每步迭代仅需做一次比较判断，有两个分支
Rank mi = ( lo + hi ) >> 1; //以中点为轴点（区间宽度的折半，等效于宽度之数值表示的右移）
( e < _elem[mi] ) ? hi = mi : lo = mi + 1; //经比较后确定深入[lo, mi)或(mi, hi)
} //成功查找不能提前终止
return lo - 1; //循环结束时，lo为大于e的元素的最小秩，故lo - 1即不大于e的元素的最大秩
} //有多个命中元素时，总能保证返回秩最大者；查找失败时，能够返回失败的位置
2，斐波那契查找（Fibonacci search）
这个点是：黄金分割比率的点
- 优点：把轴点定的比中间点靠后，尽量让查找的值在左侧，所以减少了一次比较
template <typename T> static Rank fibSearch ( T* S, T const& e, Rank lo, Rank hi ) {
for( Fib fib ( hi - lo ); lo < hi; ) { //Fib数列制表备查
while( hi - lo < fib.get() ) fib.prev(); //自后向前顺序查找（分摊O(1)）
Rank mi = lo + fib.get() - 1; //确定形如Fib(k) - 1的轴点
( e < S[mi] ) ? hi = mi : lo = mi + 1; //比较后确定深入前半段[lo, mi)或后半段(mi, hi)
} //成功查找不能提前终止
return --lo; //循环结束时，lo为大于e的元素的最小秩，故lo - 1即不大于e的元素的最大秩
} //有多个命中元素时，总能保证返回最秩最大者；查找失败时，能够返回失败的位置3，插值查找（interpolation search）
这个点是：mi = lo + （hi - lo）* （e - A[lo]）/ (A[hi] - A[lo])
- 优点：如果值是大致的线性分布，就可以通过索引的比率，找到一个更近的点，收缩更快，效率明显高于二分和斐波那契。比如英文字典，如果要查B开头的单词，肯定就一下就翻前面的页，如果查Y开头的，肯定就翻靠后的页，插值查找就是这个原理。
- 缺点：如果不是线性分布，就会退化成顺序查找，效率大大降低。
问题：在什么情况下，使用适当的查找算法呢？
- 情景1：假如在一个非常大的空间查找时，先使用插值查找，收缩到一定小的空间后，再使用二分或者斐波那契查找。
- 情景2：假如小的空间查找时，使用二分或者斐波那契。
c/c++ 学习互助QQ群：877684253
本人微信：xiaoshitou5854
内容总结
以上是互联网集市为您收集整理的算法 在连续线性空间里查找全部内容，希望文章能够帮你解决算法 在连续线性空间里查找所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。
来源：【匿名】