顺序查找和二分法查找
顺序查找:对表中的元素排序无要求,但如果表中各个元素的查找概率并不相等,则应先对元素的查找概率进行排序,使表中元素的查找概率由小到大重新排列,以便提高查找概率。
二分法查找:折半查找的效率比顺序查找高,但折半查找只适用于有序表,且限于顺序存储结构(对链式存储无效)。
typedef int ElemType;
//遍历输出容器对象
void print_vector(vector<ElemType> &vec){
for(vector<ElemType>::iterator it=vec.begin(); it!=vec.end(); ++it)
cout<<setw(5)<<*it;
cout<<endl;
}
//顺序查找,返回索引值
int Search_Seq(vector<ElemType> &vec, ElemType key){
vec[0] = key; //第1个元素作为哨兵
vector<ElemType>::reverse_iterator it = vec.rbegin();
for(; *it!=key; ++it); //逆序查找
return vec.rend()-it; //返回1表示找不到指定元素
}
//二分法查找,只适用于有序序列
int Search_Bin(vector<ElemType> &vec, ElemType key){
vector<ElemType>::iterator low, high, mid;
low = vec.begin();
high = vec.end()-1;
while(low <= high){
mid = low+(high-low)/2;
if(*mid == key)return mid-vec.begin()+1;
else if(*mid > key)high = mid - 1;
else low = mid + 1;
}
return 1;
}
int main()
{
//演示
vector<ElemType> vec(11);
for(int n=1; n<=10; ++n)
vec[n] = 2*n+1;
print_vector(vec);
cout<<"顺序查找"<<endl;
cout<<Search_Seq(vec,13)<<endl;
cout<<"二分法查找"<<endl;
cout<<Search_Bin(vec,13)<<endl;
return 0;
}
结果:
0 3 5 7 9 11 13 15 17 19 21
顺序查找
7
二分法查找
7
假设序列中有n个元素,且每个元素的查找概率相等,则
顺序查找的平均查找长度为:(n+1)/2;二分法的平均查找长度为:log(n+1)-1。
当然,上面是假设成功查找时的情况。如果待查找的元素不存在,则顺序查找的查找长度为(n+1);二分法的查找长度为 :[log(n)]+1。
分享到:
相关推荐
1. 掌握顺序查找、二分法查找的算法。3. 创建一棵二叉搜索树,给出查找元素x的算法
二分法查找和顺序查找 排序后二分法
包括顺序查找和二分法查找两种查找方法,实现函数均已放入头文件中。
与顺序查找相比,二分法查找的时间复杂度更低,适用于大规模数据的查找。但是,二分法查找要求数组必须是有序的,如果数组无序,则需要先进行排序操作。 总之,二分法查找是一种常用的查找算法,适用于有序数组中...
数据结构 C语言版 生成随机数,随机数组成的顺序表进行查找操作 二分法排序,快速排序
很显然,折半查找法相对于其他查找方法例如顺序查找法效率要高很多; 下面我们来实际操作一下,了解二分查找的奥义。 例如:要在数组arr[]={8,7,9,6,4,1,2,5,3,10,11};中查找key=7的位置;首先,我们要先将数组arr中...
编写程序对数据序列采用二分查找法和顺序查找法查找元素的下标,要求使用类模板实现(其中二分法查找算法要求用递归实现,给定数据序列有序)。
C语言版数据结构中利用二分查找实现在顺序表的查找。同时包含循序表的插入等操作。
(1)掌握顺序查找,二分法查找和索引查找的算法思想及程序实现方法。 (2)掌握二叉排序树、AVL树的查找、插入、删除、建立算法的思想及程序实现方法。 (3)掌握散列存储结构的思想,能选择合适散列函数,实现...
C++课程设计数据查找,包括:顺序查找 、二分法查找、索引查找、散列查找
数据结构 查找实验报告 1、在顺序表中查找某个数据,若查找成功输出其位置及查找次数,若...(2)在该顺序表上用二分法查找某个数据,若查找成功输出其位置及查找次数,若查找失败输出失败信息、比较次数和应插入的位置
查找相关算法,包含完整源码,在vs2013调试通过
复制代码 代码如下: <?php /** * 查找 * **/ // 顺序查找 function normal_search($arrData,$val) { $len = count($arrData); if($len == 0) return -1; for($i = 0;$i <... } // 测试顺序查找
很好用的查找方法学习资料, 经过整理和测试运行... 里面讲解丰富
数据结构 作业题目 查找 顺序查找 二分法查找 搜索树查找
也称顺序查找法,基本思想: 11 22 43 90 4 90 56 49 -10 3 0 1 2 3 4 5 6 7 8 9 将要查找的对象(关键字key)与数组中每个元素逐一比较,如果某一元素值与关键词key相等,则表示查找成功,返回元素的位置;如果没有...
排序、二分法查找、树遍历等常见算法实现python语言实现 常见数据结构 顺序表 Python中的list和tuple两种类型采用了顺序表的实现技术 链表 单向链表 双向链表 单向循环链表 栈 队列 FIFO队列 LIFO队列 优先队列...
C 二分查找算法源码实例,编写程序对数据序列采用二分查找法和顺序查找法查找元素的下标,要求使用类模板实现(其中二分法查找算法要求用递归实现,给定数据序列有序)。
⑦按房号查询(顺序查找) 本宿舍管理查询软件是为了方便宿舍管理人员实现宿舍管理查询而开发的,具有信息录入,输入信息、学号、房号,用程序实现按姓名排序、学号排序、房号排序,按姓名查找、学号查找,房号查找...