宁波网站推广方式定制公司,西宁网站建设平台公司,成都网站建设_创新互联,贵阳网站制作工具find_binary函数
注意事项#xff1a;
#xff08;1#xff09;你设计的迭代器模板中必须有using value_type T#xff0c;且有加减运算功能#xff0c;其本上能与C标准库std中一样。 #xff08;2#xff09;集合必须是有序的。 下面是函数代码#xff1a;
///
1你设计的迭代器模板中必须有using value_type T且有加减运算功能其本上能与C标准库std中一样。 2集合必须是有序的。 下面是函数代码
/// summary
/// 二分法查找有序表的通用算法可查链表数组字符串...等等
/// 例子
/// vectorint v;
/// find_binary(b.begin(),v.end(),3); // Inde返回 (-1, *Iterator ?)
///
/// vectorint v {3};
/// find_binary(b.begin(),v.end(),3); // 返回 (Index 0, *Iterator 3)
///
/// const char* sz abcdefgb;
/// auto f3 lf::find_binary(sz, sz 8, c); //返回 (Index 2, *Iterator c)
/// /summary
/// typeparam nameIteratorType迭代器类型/typeparam
/// typeparam namevalue_type值类型/typeparam
/// param nameitBegin开始位置/param
/// param nameitEnd结束位置/param
/// param namevtFindValue查找值/param
/// returns返回索引与指向vtFindValue的迭代器/returns
/// 创建时间 2024-07-03 最后一修改时间2024-07-03 (基本上已经测试
templatetypename IteratorType,typename value_type IteratorType::value_type
FindResultIteratorType find_binary(const IteratorType itBegin, const IteratorType itEnd, const value_type vtFindValue)
{FindResultIteratorType fr; auto beg itBegin;auto end itEnd;int nCount end - beg;if (nCount 0) return fr;if (*(itEnd-1) *itBegin) {//从小到大排列auto mid beg nCount / 2;while (mid ! itEnd){if(*mid vtFindValue){fr.Iter mid;fr.Index mid - itBegin;return fr;}if (vtFindValue *mid)end mid;elsebeg mid 1; //在mid之后查找mid beg (end - beg) / 2; //新的中间点} }else{ //从大到小排列 auto mid beg nCount / 2;while (mid ! itEnd) {if (*mid vtFindValue) {fr.Iter mid;fr.Index mid - itBegin;return fr;}if (vtFindValue *mid)end mid;elsebeg mid 1; //在mid之后查找mid beg (end - beg) / 2; //新的中间点}}return fr;
} 例子代码 int main()
{std::vectorint v1 { 1,2,3,4,5,6 ,7,8,9,10 };_DListint d1 { 1,2,3,4,5,6 ,7,8,9,10 };const char* sz abcdefgb;auto f1 lf::find_binary(v1.begin(), v1.end(), 3);cout *(f1.Iter) \n;cout f1.Index \n;cout ---------- \n;auto f2 lf::find_binary(d1.begin(), d1.end(), 3);cout *(f2.Iter) \n;cout f2.Index \n;cout ---------- \n;auto f3 lf::find_binary(sz, sz 8, c);cout *(f3.Iter) \n;cout f3.Index \n;cout ---------- \n;std::vectorint v2 { 10,9,8,7,6,5,4,3,2,1 };auto f4 lf::find_binary(v2.begin(), v2.end(), 3);cout *(f4.Iter) \n;cout f4.Index \n;cout ---------- \n;}
输出 完整代码如下
/*******************************************************************************************
文件名 _AlgorithmLibrary.h功能 算法库作者 李锋手机 13828778863Email ruizhilf139.com创建时间 2024年07月02日最后一次修改时间 : 2024年07月02日
*********************************************************************************************/
#pragma once//Algorithm library 算法库#include _Macro.h/*****************************************************************************排序****************************************************************************///排序
//参考https://blog.csdn.net/qq_45615577/article/details/115257685//排序的概念
/*
排序所谓排序就是使一串记录按照其中的某个或某些关键字的大小递增或递减的排列起来的操作。
稳定性假定在待排序的记录序列中存在多个具有相同的关键字的记录若经过排序这些记录的相对次 序保持不变即在原序列中r[i] r[j]且r[i]在r[j]之前而在排序后的序列中r[i]仍在r[j]之前则称这种排 序算法是稳定的否则称为不稳定的。
内部排序数据元素全部放在内存中的排序。
外部排序数据元素太多不能同时放在内存中根据排序过程的要求不能在内外存之间移动数据的排序。
————————————————版权声明本文为博主原创文章遵循 CC 4.0 BY - SA 版权协议转载请附上原文出处链接和本声明。原文链接https ://blog.csdn.net/qq_45615577/article/details/115257685
*/
_LF_BEGIN_/// summary
/// 选择排序---直接选择排序
/// 每一次从待排序的数据元素中选出最小或最大的一个元素存放在序列的起始位置
/// 直到全部待排序的 数据元素排完 。
/// 找出序列中的最小关键字然后将这个元素与序列首端元素交换位置。例如序列前i个
/// 元素已经有序从第i 1到第n个元素中选择关键字最小的元素假设第j个元素为最小
/// 元素则交换第j个元素与第i 1个元素的位置。依次执行此操作直到第n - 1个元素
/// 也被确定。
/// /summary
/// typeparam nameT类型/typeparam
/// param namepData开始位置/param
/// param namenCount元素个数/param
/// param nameso排序顺序默认从小到大/param
/// 创建时间 2024-07-01 最后一修改时间2024-07-01
/// 参考网址https://blog.csdn.net/qq_45615577/article/details/115257685
templateclass T
void sort_selection(T* pData, const size_t nCount, const bool bMinMax true)
{/*7 4 5 9 8 2 11 4 5 9 8 2 72 5 9 8 4 74 9 8 5 75 8 9 77 9 88 9在 [0 , n-1] 中找出最小的放在第一位在 [1 , n-1] 中找出最小的放在第二位...*/if (pData null || nCount 0) return;int nSortedCount 0; //已排序好的个数if (bMinMax) {while (nSortedCount nCount) {int minIndex nSortedCount;//在[nStart, nCount-1] 中找出最小值for (int n nSortedCount 1; n nCount; n) {if (*(pData n) *(pData minIndex)) {minIndex n;}}if (minIndex ! nSortedCount) {T tmp *(pData minIndex);*(pData minIndex) *(pData nSortedCount);*(pData nSortedCount) tmp;}nSortedCount;}}else {while (nSortedCount nCount) {int maxIndex nSortedCount;//在[nStart, nCount-1] 中找出最大值for (int n nSortedCount 1; n nCount; n) {if (*(pData n) *(pData maxIndex)) {maxIndex n;}}if (maxIndex ! nSortedCount) {T tmp *(pData maxIndex);*(pData maxIndex) *(pData nSortedCount);*(pData nSortedCount) tmp;}nSortedCount;}}}/// summary
/// 返回最小值的位置
/// lf::_DListint d1 { 1,3,5,8,2,0 };
/// lf::_DListint d2 { 1 };
/// lf::_DListint d3 { };
/// vectorint v { 1,3,5,8,2,0 };
///
/// _pin(*lf::Min(d1.begin(), d1.end())); //输出 0
/// _pin(*lf::Min(d2.begin(), d2.end())); //输出 1
/// _pin(*lf::Min(d3.begin(), d3.end())); //报错最少一个元素
///
/// _pin(*lf::Min(v.begin(), v.end())); //输出 0
///
/// _string s _t(sdwsffa);
/// _pin(*lf::Min(s.begin(), s.end())); //输出 a/// /summary
/// typeparam nameIteratorClass/typeparam
/// param nameitBegin/param
/// param nameitEnd/param
/// returns/returns
/// 创建时间 2024-07-02 最后一修改时间2024-07-02
templatetypename IteratorClass
IteratorClass Min(IteratorClass itBegin, IteratorClass itEnd) {assert(itBegin ! itEnd);IteratorClass result itBegin;while (itBegin ! itEnd) {if (*result *itBegin)result itBegin;itBegin;}return result;
}/// summary
///
/// /summary
/// typeparam nameIteratorClass/typeparam
/// param nameitBegin/param
/// param nameitEnd/param
/// returns/returns
/// 创建时间 2024-07-02 最后一修改时间2024-07-02
templatetypename IteratorClass
IteratorClass Max(IteratorClass itBegin, IteratorClass itEnd) {assert(itBegin ! itEnd);IteratorClass result itBegin;while (itBegin ! itEnd) {if (*result *itBegin)result itBegin;itBegin;}return result;
}/// summary
///
/// /summary
/// typeparam nameIteratorClass/typeparam
/// param nameit1/param
/// param nameit2/param
/// 创建时间 2024-07-02 最后一修改时间2024-07-02
templatetypename IteratorClass
void Swap(IteratorClass it1, IteratorClass it2) {//std::cout \n;//_pin(*it1);//_pin(*it2);auto tmp *it1; //如果*it2是 int 则tmp 的类型是int, 并不是int。*it1 *it2;*it2 tmp;//_pin(*it1);//_pin(*it2);//std::cout \n;
}/// summary
/// lf::_DListint d4 {1,2,3,6,5,4};
/// lf::sort_selection(d4.begin(), d4.end(), _SortOrder::s_Minmax);
/// _pcn(d4); //输出d4{1,2,3,4,5,6}
/// lf::sort_selection(d4.begin(), d4.end(), _SortOrder::s_Maxmin);
/// _pcn(d4); //输出d4{6,5,4,3,2,1}
///
/// _string s2 _t(_DListNodeIterator,abcd,efg);
/// _pcn(s2); //s2_DListNodeIterator,abcd,efg
/// lf::sort_selection(s2.begin(), s2.end(), _SortOrder::s_Minmax);
/// _pcn(s2); //s2,,DILN_aabcddeeefgioorrsttt
/// lf::sort_selection(s2.begin(), s2.end(), _SortOrder::s_Maxmin);
/// _pcn(s2); //s2tttsrrooigfeeeddcbaa_NLID,,
/// /summary
/// typeparam nameIteratorClass/typeparam
/// param nameitBegin/param
/// param nameitEnd/param
/// param nameso/param
/// 创建时间 2024-07-01 最后一修改时间2024-07-02已测试
templatetypename IteratorClass
void sort_selection(IteratorClass itBegin, IteratorClass itEnd, const bool bMinMax true)
{/*7 4 5 9 8 2 11 4 5 9 8 2 72 5 9 8 4 74 9 8 5 75 8 9 77 9 88 97 2 2 2 2 2 22 7 2 2 2 2 22 7 2 2 2 22 7 2 2 22 7 2 22 7 22 7在 [0 , n-1] 中找出最小的放在第一位在 [1 , n-1] 中找出最小的放在第二位...*/if (bMinMax) {while (itBegin ! itEnd) {//在[itBegin 1, itEnd] 中找出最小值,与itBegin交换 Swap(itBegin, Min(itBegin, itEnd));itBegin;}}else {while (itBegin ! itEnd) {//在[itBegin 1, itEnd] 中找出最小值,与itBegin交换Swap(itBegin, Max(itBegin, itEnd));itBegin;}}
}/*****************************************************************************查找顺序查找二分查找插值查找、斐波那契查找分块查找哈希查找树表查找****************************************************************************/
templatetypename IteratorType
struct FindResult
{/// summary/// 如果没找到 Index -1/// /summaryint Index;IteratorType Iter;public:inline FindResult(){Index -1;}inline FindResult(const FindResult r){Index r.Index;Iter r.Iter;}
};/// summary
/// 顺序查找
///
/// 注意
/// 如果是向后查找则返回的索引是以itFirst开始算来第一个为 0即itFirst为0。
/// 如果是向前揸找则返回的索引是以itLast开始算起第一个即itLast为0。
///
/// /summary
/// typeparam nameIteratorType/typeparam
/// typeparam nameDataType/typeparam
/// param nameitBegin/param
/// param nameitEnd/param
/// param nametValue/param
/// param namebBackward/param
/// returns/returns
/// 创建时间 2024-07-03 最后一修改时间2024-07-03
templatetypename IteratorType, typename DataType
FindResultIteratorType find_sequential(IteratorType itFirst, IteratorType itLast,const DataType tFindValue, const bool bBackward true)
{FindResultIteratorType fr;fr.Index -1;int n 0;if (bBackward) { //向后while (true){if (*itFirst tFindValue) {fr.Index n;fr.Iter itFirst;break;}n;itFirst;if (itFirst itLast) break;}}else {while (true){if (*itLast tFindValue) {fr.Index n;fr.Iter itLast;break;}n;--itLast;if (itFirst itLast) break;}}return fr;
}/// summary
/// 集合类必须带有 begin() 和 end() 函数
/// 例子
/// std::vectorint v { 1,2,3,23,435,4646,34 };
/// lf::_DListint d { 1,2,3,23,435,4646,34 };
/// if (lf::IsExists(d, 23))
/// {
/// cout 存在23.\n;
/// }
/// if (lf::IsExists(v, 55))
/// {
/// cout 存在55.\n;
/// }
/// /summary
/// typeparam namevalue_type/typeparam
/// typeparam nameCollectionClass/typeparam
/// param namecol/param
/// param namevalue/param
/// returns/returns
/// 创建时间 2024-07-03 最后一修改时间2024-07-03
templatetypename CollectionClass, typename value_type CollectionClass::value_type
bool IsExists(const CollectionClass col, const value_type value)
{auto itbegin col.begin();auto itend col.end();while (itbegin ! itend){if (*itbegin value)return true;itbegin;}return false;
}/// summary
/// 二分法查找有序表的通用算法可查链表数组字符串...等等
/// 例子
/// vectorint v;
/// find_binary(b.begin(),v.end(),3); // Inde返回 (-1, *Iterator ?)
///
/// vectorint v {3};
/// find_binary(b.begin(),v.end(),3); // 返回 (Index 0, *Iterator 3)
///
/// const char* sz abcdefgb;
/// auto f3 lf::find_binary(sz, sz 8, c); //返回 (Index 2, *Iterator c)
/// /summary
/// typeparam nameIteratorType迭代器类型/typeparam
/// typeparam namevalue_type值类型/typeparam
/// param nameitBegin开始位置/param
/// param nameitEnd结束位置/param
/// param namevtFindValue查找值/param
/// returns返回索引与指向vtFindValue的迭代器/returns
/// 创建时间 2024-07-03 最后一修改时间2024-07-04 (初步测试
templatetypename IteratorType,typename value_type IteratorType::value_type
FindResultIteratorType find_binary(const IteratorType itBegin, const IteratorType itEnd, const value_type vtFindValue)
{FindResultIteratorType fr; auto beg itBegin;auto end itEnd;int nCount end - beg;if (nCount 0) return fr;if (*(itEnd-1) *itBegin) {//从小到大排列auto mid beg nCount / 2;while (mid ! itEnd){if(*mid vtFindValue){fr.Iter mid;fr.Index mid - itBegin;return fr;}if (vtFindValue *mid)end mid;elsebeg mid 1; //在mid之后查找mid beg (end - beg) / 2; //新的中间点} }else{ //从大到小排列 auto mid beg nCount / 2;while (mid ! itEnd) {if (*mid vtFindValue) {fr.Iter mid;fr.Index mid - itBegin;return fr;}if (vtFindValue *mid)end mid;elsebeg mid 1; //在mid之后查找mid beg (end - beg) / 2; //新的中间点}}return fr;
}_LF_END_
