您當前位置：首頁 > php開源 > php教程 > 數據結構基礎(2) --順序查找 & 二分查找

數據結構基礎(2) --順序查找 & 二分查找

來源：程序員人生發布時間：2015-01-06 09:01:05 閱讀次數：3286次

順序查找

適用范圍:

沒有進行排序的數據序列

缺點:

速度非常慢, 效力為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, 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 由于在后續的查找進程中,可能會以下操作 (*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, 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分查找

算法思想猶如迭代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 ⑴; }

小結:

其實C++ 的STL已實現好了std::binary_search(),在用的時候我們只需調用便可, 但是2分算法的思想還是非常重要的, 在求解1些較為復雜的問題時, 我們經常能夠看到2分的身影.

生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
程序員人生