find_binary函数
注意事项:
(1)你设计的迭代器模板中必须有using value_type = T,且有加减运算功能,其本上能与C++标准库std中一样。
(2)集合必须是有序的。
下面是函数代码:
/// <summary>
/// 二分法查找有序表的通用算法(可查链表,数组,字符串...等等)
/// 例子:
/// vector<int> v;
/// find_binary(b.begin(),v.end(),3); // Inde返回 (-1, *Iterator == ?)
///
/// vector<int> 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 name="IteratorType">迭代器类型</typeparam>
/// <typeparam name="value_type">值类型</typeparam>
/// <param name="itBegin">开始位置</param>
/// <param name="itEnd">结束位置</param>
/// <param name="vtFindValue">查找值</param>
/// <returns>返回索引与指向vtFindValue的迭代器</returns>
/// 创建时间: 2024-07-03 最后一修改时间:2024-07-03 (基本上已经测试)
template<typename IteratorType,typename value_type = IteratorType::value_type>
FindResult<IteratorType> find_binary(const IteratorType& itBegin,
const IteratorType& itEnd, const value_type& vtFindValue)
{
FindResult<IteratorType> 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;
else
beg = 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;
else
beg = mid + 1; //在mid之后查找
mid = beg + (end - beg) / 2; //新的中间点
}
}
return fr;
}
例子代码:
int main()
{
std::vector<int> v1 = { 1,2,3,4,5,6 ,7,8,9,10 };
_DList<int> 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::vector<int> 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
功能 : 算法库
作者 : 李锋
手机 : 13828778863
Email : ruizhilf@139.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 name="T">类型</typeparam>
/// <param name="pData">开始位置</param>
/// <param name="nCount">元素个数</param>
/// <param name="so">排序顺序,默认从小到大</param>
/// 创建时间: 2024-07-01 最后一修改时间:2024-07-01
/// 参考网址:https://blog.csdn.net/qq_45615577/article/details/115257685
template<class T>
void sort_selection(T* pData, const size_t& nCount, const bool& bMinMax = true)
{
/*
7 4 5 9 8 2 1
1 4 5 9 8 2 7
2 5 9 8 4 7
4 9 8 5 7
5 8 9 7
7 9 8
8 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::_DList<int> d1 = { 1,3,5,8,2,0 };
/// lf::_DList<int> d2 = { 1 };
/// lf::_DList<int> d3 = { };
/// vector<int> 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 name="IteratorClass"></typeparam>
/// <param name="itBegin"></param>
/// <param name="itEnd"></param>
/// <returns></returns>
/// 创建时间: 2024-07-02 最后一修改时间:2024-07-02
template<typename 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 name="IteratorClass"></typeparam>
/// <param name="itBegin"></param>
/// <param name="itEnd"></param>
/// <returns></returns>
/// 创建时间: 2024-07-02 最后一修改时间:2024-07-02
template<typename 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 name="IteratorClass"></typeparam>
/// <param name="it1"></param>
/// <param name="it2"></param>
/// 创建时间: 2024-07-02 最后一修改时间:2024-07-02
template<typename 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::_DList<int> 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); //s2=tttsrrooigfeeeddcbaa_NLID,,
/// </summary>
/// <typeparam name="IteratorClass"></typeparam>
/// <param name="itBegin"></param>
/// <param name="itEnd"></param>
/// <param name="so"></param>
/// 创建时间: 2024-07-01 最后一修改时间:2024-07-02(已测试)
template<typename IteratorClass>
void sort_selection(IteratorClass itBegin, IteratorClass itEnd, const bool& bMinMax = true)
{
/*
7 4 5 9 8 2 1
1 4 5 9 8 2 7
2 5 9 8 4 7
4 9 8 5 7
5 8 9 7
7 9 8
8 9
7 2 2 2 2 2 2
2 7 2 2 2 2 2
2 7 2 2 2 2
2 7 2 2 2
2 7 2 2
2 7 2
2 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;
}
}
}
/*****************************************************************************
查找
顺序查找
二分查找
插值查找、
斐波那契查找
分块查找
哈希查找
树表查找
****************************************************************************/
template<typename IteratorType>
struct FindResult
{
/// <summary>
/// 如果没找到 Index == -1
/// </summary>
int 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 name="IteratorType"></typeparam>
/// <typeparam name="DataType"></typeparam>
/// <param name="itBegin"></param>
/// <param name="itEnd"></param>
/// <param name="tValue"></param>
/// <param name="bBackward"></param>
/// <returns></returns>
/// 创建时间: 2024-07-03 最后一修改时间:2024-07-03
template<typename IteratorType, typename DataType>
FindResult<IteratorType> find_sequential(IteratorType itFirst, IteratorType itLast,
const DataType& tFindValue, const bool& bBackward = true)
{
FindResult<IteratorType> 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::vector<int> v = { 1,2,3,23,435,4646,34 };
/// lf::_DList<int> 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 name="value_type"></typeparam>
/// <typeparam name="CollectionClass"></typeparam>
/// <param name="col"></param>
/// <param name="value"></param>
/// <returns></returns>
/// 创建时间: 2024-07-03 最后一修改时间:2024-07-03
template<typename 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>
/// 二分法查找有序表的通用算法(可查链表,数组,字符串...等等)
/// 例子:
/// vector<int> v;
/// find_binary(b.begin(),v.end(),3); // Inde返回 (-1, *Iterator == ?)
///
/// vector<int> 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 name="IteratorType">迭代器类型</typeparam>
/// <typeparam name="value_type">值类型</typeparam>
/// <param name="itBegin">开始位置</param>
/// <param name="itEnd">结束位置</param>
/// <param name="vtFindValue">查找值</param>
/// <returns>返回索引与指向vtFindValue的迭代器</returns>
/// 创建时间: 2024-07-03 最后一修改时间:2024-07-04 (初步测试)
template<typename IteratorType,typename value_type = IteratorType::value_type>
FindResult<IteratorType> find_binary(const IteratorType& itBegin,
const IteratorType& itEnd, const value_type& vtFindValue)
{
FindResult<IteratorType> 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;
else
beg = 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;
else
beg = mid + 1; //在mid之后查找
mid = beg + (end - beg) / 2; //新的中间点
}
}
return fr;
}
_LF_END_