二分法查找有序表的通用算法（可查链表，数组，字符串...等等）

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_