45fan.com - 路饭网

搜索: 您的位置主页 > 网络频道 > 阅读资讯:常用查找算法的详细介绍

常用查找算法的详细介绍

2016-08-29 14:05:22 来源:www.45fan.com 【

常用查找算法的详细介绍

//search.h包含了所有的常用查找算法

//使用顺序查找法的查找函数
//seqSearch(const int arr[],int first,int last,int target)
template <typename T>
int seqSearch(const T arr[],int first,int last,const T& target)
{
int i=first;

//扫描下标范围first<=i<last; 测试是否有匹配
//或下标超出范围
while (!(i==last)&&!(arr[i]==target))
i++;

return i; //i是匹配值的下标,或者,如果没有匹配,则i=last
}

//模板函数find_last_of()的实现
template <typename T>
int find_last_of(const T arr[],int first,int last,const T& target)
{
int i=last-1;

//描扫下标范围first<=i<last;测试是否有匹配
//或下标超出范围
while(i>=first&&target!=arr[i])
i--;
if (i<first) return last; //没找到,则返回last
return i;
}

//二分查找算法函数binSearch()的实现
template <typename T>
int binSearch(const T arr[],int first,int last,const T& target)
{
int mid; //中间点的下标
T midValue; //用于保存arr[mid]元素值

int origLast=last; //保存last的初始值

while(first<last) //测试非空子表,如果是非空子表,则继续查找
{
mid=(first+last)/2;
midValue=arr[mid];
if (target==midValue) //有一个匹配
return mid;
//确定要查找哪个子表
else if(target<midValue)
last=mid;
else
first=mid+1; //查找子表的后半部分,重新设置first
}
return origLast; //没有找到目标值
}

 

 

本文地址:http://www.45fan.com/a/question/69325.html
Tags: 算法 查找 search.h
编辑:路饭网
关于我们 | 联系我们 | 友情链接 | 网站地图 | Sitemap | App | 返回顶部