# 数据结构基础(2) –顺序查找 & 二分查找

## 顺序查找

//实现
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分查找

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, Type *end, const Type &searchValue)
throw(std::range_error)
{
if ((begin == end) || (begin == NULL) || (end == NULL))
throw std::range_error("pointer unavailable");

/**注意:此处high为end⑴,其实不是end

*/
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, int length, const Type &searchValue)
throw(std::range_error)
{
return binarySearch(array, array+length, searchValue);
}

## 递归简介

//递归求解斐波那契数列
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分查找

//实现
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, mid⑴, searchValue);
else
return binarySearchByRecursion(array, mid+1, right, searchValue);
}

return ⑴;
}

1. 本站所有资源来源于用户上传和网络，如有侵权请邮件联系站长！
2. 分享目的仅供大家学习和交流，您必须在下载后24小时内删除！
3. 不得使用于非法商业用途，不得违反国家法律。否则后果自负！
4. 本站提供的源码、模板、插件等等其他资源，都不包含技术服务请大家谅解！
5. 如有链接无法下载、失效或广告，请联系管理员处理！
6. 本站资源售价只是赞助，收取费用仅维持本站的日常运营所需！
7. 本站源码并不保证全部能正常使用，仅供有技术基础的人学习研究，请谨慎下载
8. 如遇到加密压缩包，请使用WINRAR解压,如遇到无法解压的请联系管理员！