RLib  5.7
RLib - an opensource, lightweight and multi-platform framework for cpp programming
System::Generic::Search Namespace Reference

Provides several static methods for searching More...

Functions

template<typename R = intptr_t, typename Collections::Generic::IComparer< R >::EqualsDelegate equals = Collections::Generic::IComparer<R>::Equals>
intptr_t sequential_search (const R list[], intptr_t _lower, intptr_t _upper, const R &key)
 顺序搜索法(Sequential Search) 优点: 该方法对数据无事先排序(Sorting)要求, 容易实现 缺点: 搜索效率差(平均搜索 (N + 1) / 2 次), 不管是否排序, 每次都必须从头到尾遍历一次 时间复杂度: 如果没有重复数据,线性查找在找到任一元素时就终止,否则需要全部遍历. 在最差情況下, 需作N次比较, O(N) 在平均狀況下(各元素出现与分布的概率相等)需 (N + 1) / 2次比较,所以最差时间为O(N), 最好时间为O(1) = 1次 More...
 
template<typename R = intptr_t>
intptr_t sequential_search (const R list[], intptr_t _lower, intptr_t _upper, const R &key, typename Collections::Generic::IComparer< R >::EqualsDelegate equals)
 
template<typename R = intptr_t, typename Collections::Generic::IComparer< R >::EqualsDelegate equals = Collections::Generic::IComparer<R>::Equals>
intptr_t sequential_search_end (const R list[], intptr_t _lower, intptr_t _upper, const R &key)
 
template<typename R = intptr_t>
intptr_t sequential_search_end (const R list[], intptr_t _lower, intptr_t _upper, const R &key, typename Collections::Generic::IComparer< R >::EqualsDelegate equals)
 
template<typename R = intptr_t, typename Collections::Generic::IComparer< R >::Delegate compare = Collections::Generic::IComparer<R>::Compare>
intptr_t binary_search (const R list[], intptr_t _lower, intptr_t _upper, const R &key)
 二分搜索法(Binary Search) 优点: 搜索效率优(平均搜索 Log2N 次) 缺点: 数据必需事先排序且必需可直接随机存取 时间复杂度: 每次比较都会比上一次少一半数据, 2^x = N, x = Log2N, 因此平均时间 O(LogN) More...
 
template<typename R = intptr_t>
intptr_t binary_search (const R list[], intptr_t _lower, intptr_t _upper, const R &key, typename Collections::Generic::IComparer< R >::Delegate compare)
 
template<typename R = intptr_t, typename Collections::Generic::IComparer< R >::Delegate compare = Collections::Generic::IComparer<R>::Compare>
intptr_t binary_search_recursively (const R *list, intptr_t _lower, intptr_t _upper, const R &key)
 
template<typename R = intptr_t>
intptr_t interpolation_search (const R *list, intptr_t _lower, intptr_t _upper, const R &key)
 插值搜索法(Interpolation Search) 定义: 二分搜索法的一种改进, 依照数据位置分布, 运用插值预测数据所在位置, 再以二分法方式逼近 插值是离散函数逼近的重要方法, 利用它可通过函数在有限个点处的取值状况, 估算出函数在其他点处的近似值 优点: 数据分布均匀时搜索速度极快 缺点: 数据必需事先排序且需计算预测公式 时间复杂度: 取决于数据分布情形, 平均时间 O(LogLogN) 优于 二分搜索 O(LogN) More...
 
template<typename R = intptr_t>
intptr_t fbonacci_search (const R *list, intptr_t _lower, intptr_t _upper, const R &key)
 斐波那契搜索法(Fbonacci Search) 定义: 利用斐波那契数列的性质(黄金分割原理)预测数据所在位置, 再以二分法方式逼近 优点: 只涉及加法和减法运算 缺点: 数据必需事先排序且需计算或者预定义斐波那契数列 时间复杂度: 同于二分搜索 O(LogN), 平均情况下, 斐波那契查找优于二分查找, 但最坏情况下则劣于二分查找 More...
 
template<typename R = intptr_t>
intptr_t tree_search (const R *list, intptr_t _lower, intptr_t _upper, const R &key)
 二叉树搜索 More...
 

Detailed Description

Provides several static methods for searching

Function Documentation

template<typename R = intptr_t, typename Collections::Generic::IComparer< R >::Delegate compare = Collections::Generic::IComparer<R>::Compare>
intptr_t System::Generic::Search::binary_search ( const R  list[],
intptr_t  _lower,
intptr_t  _upper,
const R &  key 
)

二分搜索法(Binary Search) 优点: 搜索效率优(平均搜索 Log2N 次) 缺点: 数据必需事先排序且必需可直接随机存取 时间复杂度: 每次比较都会比上一次少一半数据, 2^x = N, x = Log2N, 因此平均时间 O(LogN)

template<typename R = intptr_t>
intptr_t System::Generic::Search::fbonacci_search ( const R *  list,
intptr_t  _lower,
intptr_t  _upper,
const R &  key 
)

斐波那契搜索法(Fbonacci Search) 定义: 利用斐波那契数列的性质(黄金分割原理)预测数据所在位置, 再以二分法方式逼近 优点: 只涉及加法和减法运算 缺点: 数据必需事先排序且需计算或者预定义斐波那契数列 时间复杂度: 同于二分搜索 O(LogN), 平均情况下, 斐波那契查找优于二分查找, 但最坏情况下则劣于二分查找

template<typename R = intptr_t>
intptr_t System::Generic::Search::interpolation_search ( const R *  list,
intptr_t  _lower,
intptr_t  _upper,
const R &  key 
)

插值搜索法(Interpolation Search) 定义: 二分搜索法的一种改进, 依照数据位置分布, 运用插值预测数据所在位置, 再以二分法方式逼近 插值是离散函数逼近的重要方法, 利用它可通过函数在有限个点处的取值状况, 估算出函数在其他点处的近似值 优点: 数据分布均匀时搜索速度极快 缺点: 数据必需事先排序且需计算预测公式 时间复杂度: 取决于数据分布情形, 平均时间 O(LogLogN) 优于 二分搜索 O(LogN)

template<typename R = intptr_t, typename Collections::Generic::IComparer< R >::EqualsDelegate equals = Collections::Generic::IComparer<R>::Equals>
intptr_t System::Generic::Search::sequential_search ( const R  list[],
intptr_t  _lower,
intptr_t  _upper,
const R &  key 
)

顺序搜索法(Sequential Search) 优点: 该方法对数据无事先排序(Sorting)要求, 容易实现 缺点: 搜索效率差(平均搜索 (N + 1) / 2 次), 不管是否排序, 每次都必须从头到尾遍历一次 时间复杂度: 如果没有重复数据,线性查找在找到任一元素时就终止,否则需要全部遍历. 在最差情況下, 需作N次比较, O(N) 在平均狀況下(各元素出现与分布的概率相等)需 (N + 1) / 2次比较,所以最差时间为O(N), 最好时间为O(1) = 1次

template<typename R = intptr_t>
intptr_t System::Generic::Search::tree_search ( const R *  list,
intptr_t  _lower,
intptr_t  _upper,
const R &  key 
)

二叉树搜索