Chinaunix首页 | 论坛 | 博客
  • 博客访问: 35337
  • 博文数量: 10
  • 博客积分: 246
  • 博客等级: 二等列兵
  • 技术积分: 155
  • 用 户 组: 普通用户
  • 注册时间: 2011-10-02 10:56
文章分类
文章存档

2012年(10)

我的朋友

分类: C/C++

2012-11-05 15:53:43


顺序查找和二分法查找

顺序查找:对表中的元素排序无要求,但如果表中各个元素的查找概率并不相等,则应先对元素的查找概率进行排序,使表中元素的查找概率由小到大重新排列,以便提高查找概率。
二分法查找:折半查找的效率比顺序查找高,但折半查找只适用于有序表,且限于顺序存储结构(对链式存储无效)。

假设序列中有n个元素,且每个元素的查找概率相等,则顺序查找的平均查找长度为:(n+1)/2;二分法的平均查找长度为:log(n+1)-1。
当然,上面是假设成功查找时的情况。如果待查找的元素不存在,则顺序查找的查找长度为(n+1);二分法的查找长度为 :[log(n)]+1。

点击(此处)折叠或打开

  1. typedef int ElemType;
  2. //遍历输出容器对象
  3. void print_vector(vector<ElemType> &vec){
  4.     for(vector<ElemType>::iterator it=vec.begin(); it!=vec.end(); ++it)
  5.         cout<<setw(5)<<*it;
  6.     cout<<endl;
  7. }
  8.   
  9. //顺序查找,返回索引值
  10. int Search_Seq(vector<ElemType> &vec, ElemType key){
  11.     vec[0] = key; //第1个元素作为哨兵
  12.     vector<ElemType>::reverse_iterator it = vec.rbegin();
  13.     for(; *it!=key; ++it); //逆序查找
  14.     return vec.rend()-it; //返回1表示找不到指定元素
  15. }
  16.   
  17. //二分法查找,只适用于有序序列
  18. int Search_Bin(vector<ElemType> &vec, ElemType key){
  19.     vector<ElemType>::iterator low, high, mid;
  20.     low = vec.begin();
  21.     high = vec.end()-1;
  22.     while(low <= high){
  23.         mid = low+(high-low)/2;
  24.         if(*mid == key)return mid-vec.begin()+1;
  25.         else if(*mid > key)high = mid - 1;
  26.         else low = mid + 1;
  27.     }
  28.     return 1;
  29. }
  30.   
  31. int main()
  32. {
  33.     //演示
  34.     vector<ElemType> vec(11);
  35.     for(int n=1; n<=10; ++n)
  36.         vec[n] = 2*n+1;
  37.     print_vector(vec);
  38.     cout<<"顺序查找"<<endl;
  39.     cout<<Search_Seq(vec,13)<<endl;
  40.     cout<<"二分法查找"<<endl;
  41.     cout<<Search_Bin(vec,13)<<endl;
  42.   
  43.     return 0;
  44. }

阅读(682) | 评论(0) | 转发(1) |
0

上一篇:哈希表

下一篇:Singleton设计模式

给主人留下些什么吧!~~