常用查找算法的详细介绍
//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; //没有找到目标值 }