数据结构基础(2) --顺序查找 & 二分查找
发布时间：2020-12-13 20:11:03 所属栏目：PHP教程 来源：网络整理
导读：顺序查找 适用范围: 没有进行排序的数据序列 缺点: 速度非常慢,效力为O(N) //实现template typename TypeType *sequenceSearch(Type *begin,Type *end,const Type searchValue)throw(std::range_error){ if ((begin == end) || (begin == NULL) || (end == N
顺序查找适用范围: 没有进行排序的数据序列 缺点: 速度非常慢, 效力为O(N) //实现
template <typename Type>
Type *sequenceSearch(Type *begin,Type *end,const Type &searchValue)
throw(std::range_error)
{
if ((begin == end) || (begin == NULL) || (end == NULL))
throw std::range_error("pointer unavailable");
for (Type *index = begin; index < end; ++index)
{
if (*index == searchValue)
return index;
}
return end;
}
template <typename Type>
Type *sequenceSearch(Type *array,int length,const Type &searchValue)
throw(std::range_error)
{
return sequenceSearch(array,array+length,searchValue);
} 迭代2分查找利用范围: 数据必须首先排序,才能利用2分查找;效力为(logN) 算法思想: 比方数组{1， 2， 3， 4， 5， 6， 7， 8， 9}，查找元素6，用2分查找的算法履行的话，其顺序为： 1.第1步查找中间元素，即5，由于5<6，则6必定在5以后的数组元素中，那末就在{6， 7， 8， 9}中查找， 2.寻觅{6， 7， 8， 9}的中位数，为7，7>6，则6应当在7左侧的数组元素中，那末只剩下6，即找到了。 2分查找算法就是不断将数组进行对半分割，每次拿中间元素和目标元素进行比较。 //实现:迭代2分
template <typename Type>
Type *binarySearch(Type *begin,const Type &searchValue)
throw(std::range_error)
{
if ((begin == end) || (begin == NULL) || (end == NULL))
throw std::range_error("pointer unavailable");
/**注意:此处high为end⑴,其实不是end
由于在后续的查找进程中,可能会以下操作 (*high),或等价的操作
此时应当访问的是最后1个元素,必须注意不能对数组进行越界访问!
*/
Type *low = begin,*high = end⑴;
while (low <= high)
{
//计算中间元素
Type *mid = low + (high-low)/2;
//如果中间元素的值==要找的数值,则直接返回
if (*mid == searchValue)
return mid;
//如果要找的数比中间元素大,则在数组的后半部份查找
else if (searchValue > *mid)
low = mid + 1;
//如果要找的数比中间元素小,则在数组的前半部份查找
else
high = mid - 1;
}
return end;
}
template <typename Type>
Type *binarySearch(Type *array,const Type &searchValue)
throw(std::range_error)
{
return binarySearch(array,0);">递归简介 递归就是递归...(自己调用自己),递归的是神,迭代的是人;
递归与非递归的比较 //递归求解斐波那契数列
unsigned long ficonacciRecursion(int n)
{
if (n == 1 || n == 2)
return 1;
else
return ficonacciRecursion(n⑴) + ficonacciRecursion(n⑵);
} //非递归求解斐波那契数列
unsigned long ficonacciLoop(int n)
{
if (n == 1 || n == 2)
return 1;
unsigned long first = 1,second = 1;
unsigned long ans = first + second;
for (int i = 3; i <= n; ++i)
{
ans = first + second;
first = second;
second = ans;
}
return ans;
} 递归2分查找算法思想犹如迭代2分查找; //实现
template <typename Type>
Type *binarySearchByRecursion(Type *front,Type *last,const Type &searchValue)
throw(std::range_error)
{
if ((front == NULL) || (last == NULL))
throw std::range_error("pointer unavailable");
if (front <= last)
{
Type *mid = front + (last-front)/2;
if (*mid == searchValue)
return mid;
else if (searchValue > *mid)
return binarySearchByRecursion(mid+1,last,searchValue);
else
return binarySearchByRecursion(front,mid⑴,searchValue);
}
return NULL;
}
template <typename Type>
int binarySearchByRecursion(Type *array,int left,int right,const Type &searchValue)
throw (std::range_error)
{
if (array == NULL)
throw std::range_error("pointer unavailable");
if (left <= right)
{
int mid = left + (right-left)/2;
if (array[mid] == searchValue)
return mid;
else if (searchValue < array[mid])
return binarySearchByRecursion(array,left,searchValue);
else
return binarySearchByRecursion(array,mid+1,right,searchValue);
}
return ⑴;
} 小结: 其实C++ 的STL已实现好了std::binary_search(),在用的时候我们只需调用便可, 但是2分算法的思想还是非常重要的, 在求解1些较为复杂的问题时, 我们经常能够看到2分的身影. （编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |