数据结构基础(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分 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; }

//实现 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 ⑴; }