數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)(2) --順序查找 & 二分查找
來(lái)源：程序員人生 發(fā)布時(shí)間：2015-01-06 09:01:05 閱讀次數(shù)：3279次
順序查找
適用范圍:
沒(méi)有進(jìn)行排序的數(shù)據(jù)序列
缺點(diǎn):
速度非常慢, 效力為O(N)
//實(shí)現(xià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分查找
利用范圍:
數(shù)據(jù)必須首先排序,才能利用2分查找;效力為(logN)
算法思想:
比方數(shù)組{1， 2， 3， 4， 5， 6， 7， 8， 9}，查找元素6，用2分查找的算法履行的話，其順序?yàn)椋?/span>
1.第1步查找中間元素，即5，由于5<6，則6必定在5以后的數(shù)組元素中，那末就在{6， 7， 8， 9}中查找，
2.尋覓{6， 7， 8， 9}的中位數(shù)，為7，7>6，則6應(yīng)當(dāng)在7左側(cè)的數(shù)組元素中，那末只剩下6，即找到了。
2分查找算法就是不斷將數(shù)組進(jìn)行對(duì)半分割，每次拿中間元素和目標(biāo)元素進(jìn)行比較。
//實(shí)現(xiàn):迭代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⑴,其實(shí)不是end
由于在后續(xù)的查找進(jìn)程中,可能會(huì)以下操作 (*high), 或等價(jià)的操作
此時(shí)應(yīng)當(dāng)訪問(wèn)的是最后1個(gè)元素, 必須注意不能對(duì)數(shù)組進(jìn)行越界訪問(wèn)!
*/
Type *low = begin, *high = end⑴;
while (low <= high)
{
//計(jì)算中間元素
Type *mid = low + (high-low)/2;
//如果中間元素的值==要找的數(shù)值, 則直接返回
if (*mid == searchValue)
return mid;
//如果要找的數(shù)比中間元素大, 則在數(shù)組的后半部份查找
else if (searchValue > *mid)
low = mid + 1;
//如果要找的數(shù)比中間元素小, 則在數(shù)組的前半部份查找
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);
}
遞歸簡(jiǎn)介
遞歸就是遞歸...(自己調(diào)用自己),遞歸的是神,迭代的是人;
遞歸與非遞歸的比較
//遞歸求解斐波那契數(shù)列
unsigned long ficonacciRecursion(int n)
{
if (n == 1 || n == 2)
return 1;
else
return ficonacciRecursion(n⑴) + ficonacciRecursion(n⑵);
}
//非遞歸求解斐波那契數(shù)列
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分查找;
//實(shí)現(xiàn)
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 ⑴;
}
小結(jié):
其實(shí)C++ 的STL已實(shí)現(xiàn)好了std::binary_search(),在用的時(shí)候我們只需調(diào)用便可, 但是2分算法的思想還是非常重要的, 在求解1些較為復(fù)雜的問(wèn)題時(shí), 我們經(jīng)常能夠看到2分的身影.
生活不易，碼農(nóng)辛苦
如果您覺(jué)得本網(wǎng)站對(duì)您的學(xué)習(xí)有所幫助,可以手機(jī)掃描二維碼進(jìn)行捐贈(zèng)
