顺序查找
适用范围:
没有进行排序的数据序列
缺点:
速度非常慢,效率为O(N)
[cpp]viewplaincopy在CODE上查看代码片派生到我的代码片
//实现
templatetypenameType
Type*sequenceSearch(Type*begin,Type*end,constTypesearchValue)
throw(std::range_error)
{
if((begin==end)
(begin==NULL)
(end==NULL))
throwstd::range_error("pointerunavailable");
for(Type*index=begin;indexend;++index)
{
if(*index==searchValue)
returnindex;
}
returnend;
}
templatetypenameType
Type*sequenceSearch(Type*array,intlength,constTypesearchValue)
throw(std::range_error)
{
returnsequenceSearch(array,array+length,searchValue);
}
迭代二分查找
应用范围:
数据必须首先排序,才能应用二分查找;效率为(logN)
算法思想:
譬如数组{1，2，3，4，5，6，7，8，9}，查找元素6，用二分查找的算法执行的话，其顺序为：
1.第一步查找中间元素，即5，由于56，则6必然在5之后的数组元素中，那么就在{6，7，8，9}中查找，
2.寻找{6，7，8，9}的中位数，为7，76，则6应该在7左边的数组元素中，那么只剩下6，即找到了。
二分查找算法就是不断将数组进行对半分割，每次拿中间元素和目标元素进行比较。
[cpp]viewplaincopy在CODE上查看代码片派生到我的代码片
//实现:迭代二分
templatetypenameType
Type*binarySearch(Type*begin,Type*end,constTypesearchValue)
throw(std::range_error)
{
if((begin==end)
(begin==NULL)
(end==NULL))
throwstd::range_error("pointerunavailable");
/**注意:此处high为end-1,并不是end
因为在后续的查找过程中,可能会如下操作(*high),或等价的操作
此时应该访问的是最后一个元素,必须注意不能对数组进行越界访问!
*/
Type*low=begin,*high=end-1;
while(low=high)
{
//计算中间元素
Type*mid=low+(high-low)/2;
//如果中间元素的值==要找的数值,则直接返回
if(*mid==searchValue)
returnmid;
//如果要找的数比中间元素大,则在数组的后半部分查找
elseif(searchValue*mid)
low=mid+1;
//如果要找的数比中间元素小,则在数组的前半部分查找
else
high=mid-1;
}
returnend;
}
templatetypenameType
Type*binarySearch(Type*array,intlength,constTypesearchValue)
throw(std::range_error)
{
returnbinarySearch(array,array+length,searchValue);
}
递归简介
递归就是递归...(自己调用自己),递归的是神,迭代的是人;
递归与非递归的比较
[cpp]viewplaincopy在CODE上查看代码片派生到我的代码片
//递归求解斐波那契数列
unsignedlongficonacciRecursion(intn)
{
if(n==1
n==2)
return1;
else
returnficonacciRecursion(n-1)+ficonacciRecursion(n-2);
}
[cpp]viewplaincopy在CODE上查看代码片派生到我的代码片
//非递归求解斐波那契数列
unsignedlongficonacciLoop(intn)
{
if(n==1
n==2)
return1;
unsignedlongfirst=1,second=1;
unsignedlongans=first+second;
for(inti=3;i=n;++i)
{
ans=first+second;
first=second;
second=ans;
}
returnans;
}
递归二分查找
算法思想如同迭代二分查找;
[cpp]viewplaincopy在CODE上查看代码片派生到我的代码片
//实现
templatetypenameType
Type*binarySearchByRecursion(Type*front,Type*last,constTypesearchValue)
throw(std::range_error)
{
if((front==NULL)
(last==NULL))
throwstd::range_error("pointerunavailable");
if(front=last)
{
Type*mid=front+(last-front)/2;
if(*mid==searchValue)
returnmid;
elseif(searchValue*mid)
returnbinarySearchByRecursion(mid+1,last,searchValue);
else
returnbinarySearchByRecursion(front,mid-1,searchValue);
}
returnNULL;
}
templatetypenameType
intbinarySearchByRecursion(Type*array,intleft,intright,constTypesearchValue)
throw(std::range_error)
{
if(array==NULL)
throwstd::range_error("pointerunavailable");
if(left=right)
{
intmid=left+(right-left)/2;
if(array[mid]==searchValue)
returnmid;
elseif(searchValuearray[mid])
returnbinarySearchByRecursion(array,left,mid-1,searchValue);
else
returnbinarySearchByRecursion(array,mid+1,right,searchValue);
}
return-1;
}
小结:
其实C++的STL已经实现好了std::binary_search(),在用的时候我们只需调用即可,但是二分算法的思想还是非常重要的,在求解一些较为复杂的问题时,我们时常能够看到二分的身影.
赞赏
北京白癜风的费用北京哪治疗白癜风医院收费低