順序查找

適用范圍:

沒有進行排序的數據序列

缺點:

速度非常慢,?效率為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); }

迭代二分查找

應用范圍:

數據必須首先排序,才能應用二分查找;效率為(logN)

算法思想:

譬如數組{1，?2，?3，?4，?5，?6，?7，?8，?9}，查找元素6，用二分查找的算法執行的話，其順序為：

????1.第一步查找中間元素，即5，由于5<6，則6必然在5之后的數組元素中，那么就在{6，?7，?8，?9}中查找，

????2.尋找{6，?7，?8，?9}的中位數，為7，7>6，則6應該在7左邊的數組元素中，那么只剩下6，即找到了。

????二分查找算法就是不斷將數組進行對半分割，每次拿中間元素和目標元素進行比較。

//實現:迭代二分 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-1,并不是end因為在后續的查找過程中,可能會如下操作 (*high), 或等價的操作此時應該訪問的是最后一個元素, 必須注意不能對數組進行越界訪問!*/Type *low = begin, *high = end-1;while (low <= high){//計算中間元素Type *mid = low + (high-low)/2;//如果中間元素的值==要找的數值, 則直接返回if (*mid == searchValue)return mid;//如果要找的數比中間元素大, 則在數組的后半部分查找else if (searchValue > *mid)low = mid + 1;//如果要找的數比中間元素小, 則在數組的前半部分查找elsehigh = 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;elsereturn ficonacciRecursion(n-1) + ficonacciRecursion(n-2); } //非遞歸求解斐波那契數列 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; }

遞歸二分查找

算法思想如同迭代二分查找;

//實現 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);elsereturn binarySearchByRecursion(front, mid-1, 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-1, searchValue);elsereturn binarySearchByRecursion(array, mid+1, right, searchValue);}return -1; }

小結:

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

總結

以上是生活随笔為你收集整理的数据结构基础(2) --顺序查找 二分查找的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。