【二分查找】自写二分函数的总结

news/2024/7/5 2:16:17

作者推荐

【动态规划】【广度优先搜索】LeetCode:2617 网格图中最少访问的格子数

本文涉及的基础知识点

二分查找算法合集

自写二分函数 的封装

我暂时只发现两种：
一，在左闭右开的区间寻找最后一个符合条件的元素，我封装成FindEnd函数。
二，在左开右闭的区间寻找第一个符合条件的元素，我封装成FindFirst函数。

namespace NBinarySearch
{
	template<class INDEX_TYPE,class _Pr>
	INDEX_TYPE FindFrist(INDEX_TYPE left, INDEX_TYPE rightInclue, _Pr pr)
	{
		while (rightInclue - left > 1)
		{
			const auto mid = left + (rightInclue - left) / 2;
			if (pr(mid))
			{
				rightInclue = mid;
			}
			else
			{
				left = mid;
			}
		}
		return rightInclue;
	}

	template<class INDEX_TYPE, class _Pr>
	INDEX_TYPE FindEnd(INDEX_TYPE leftInclude, INDEX_TYPE right, _Pr pr)
	{
		while (right - leftInclude > 1)
		{
			const auto mid = leftInclude + (right - leftInclude) / 2;
			if (pr(mid))
			{
				leftInclude = mid;
			}
			else
			{
				right = mid;
			}
		}
		return leftInclude;
	}
}

左闭右开 左开右闭的例子

LeetCode33: C++算法：二分查找旋转数组

class Solution {
public:
	int search(vector<int>& nums, int target) {
		int rBegin = NBinarySearch::FindFrist(-1, (int)nums.size() - 1, [&](const int mid) {return nums[mid] <= nums.back(); });
		if (target <= nums.back())
		{
			return Find(nums, rBegin, nums.size(), target);
		}
		return Find(nums, 0, rBegin, target);
	}
	int Find(const vector<int>& nums, int left, int r, int target)
	{
		int iRet = NBinarySearch::FindEnd(left,r, [&](const int mid) {return nums[mid] <= target; });
		return (target == nums[iRet]) ? iRet : -1;
	}
};
int main()
{
	vector<int> vNums = { 1,2,3,4,6 };
	auto res = Solution().search(vNums, 4);
	std::cout << "index:" << res;
	if (-1 != res)
	{
		std::cout << " value:" << vNums[res];
	}
}

左闭右开的例子

Leetcode2790:C++二分查找算法的应用：长度递增组的最大数目

namespace NBinarySearch
{
	template<class INDEX_TYPE,class _Pr>
	INDEX_TYPE FindFrist(INDEX_TYPE left, INDEX_TYPE rightInclue, _Pr pr)
	{
		while (rightInclue - left > 1)
		{
			const auto mid = left + (rightInclue - left) / 2;
			if (pr(mid))
			{
				rightInclue = mid;
			}
			else
			{
				left = mid;
			}
		}
		return rightInclue;
	}

	template<class INDEX_TYPE, class _Pr>
	INDEX_TYPE FindEnd(INDEX_TYPE leftInclude, INDEX_TYPE right, _Pr pr)
	{
		while (right - leftInclude > 1)
		{
			const auto mid = leftInclude + (right - leftInclude) / 2;
			if (pr(mid))
			{
				leftInclude = mid;
			}
			else
			{
				right = mid;
			}
		}
		return leftInclude;
	}
}

class Solution {
public:
	int maxIncreasingGroups(vector<int>& usageLimits) {
		m_c = usageLimits.size();
		m_v = usageLimits;
		sort(m_v.begin(), m_v.end());
		auto Can = [&](int len)
		{
			int i = m_c - 1;
			long long llNeed = 0;
			for (; len > 0; len--, i--)
			{
				llNeed -= (m_v[i] - len);
				if (m_v[i] >= len)
				{
					llNeed = max(0LL, llNeed);
				}
			}
			for (; i >= 0; i--)
			{
				llNeed -= m_v[i];
			}
			return llNeed <= 0;
		};
		return NBinarySearch::FindEnd(1, m_c + 1, Can);
	}
	
	int m_c;
	vector<int> m_v;
};
template<class T>
void Assert(const T& t1, const T& t2)
{
	assert(t1 == t2);
}

template<class T>
void Assert(const vector<T>& v1, const vector<T>& v2)
{
	if (v1.size() != v2.size())
	{
		assert(false);
		return;
	}
	for (int i = 0; i < v1.size(); i++)
	{
		Assert(v1[i], v2[i]);
	}
}

int main()
{
	Solution slu;
	vector<int> usageLimits;
	int res = 0;
	usageLimits = { 2,2,2 };
	res = slu.maxIncreasingGroups(usageLimits);
	Assert(res, 3);
	usageLimits = { 1,2,5 };
	res = slu.maxIncreasingGroups(usageLimits);
	Assert(res, 3);
	usageLimits = { 2,1,2 };
	res = slu.maxIncreasingGroups(usageLimits);
	Assert(res, 2);
	usageLimits = { 1,1 };
	res = slu.maxIncreasingGroups(usageLimits);
	Assert(res, 1);

	//CConsole::Out(res);
}

左闭右开的应用

C++二分查找算法的应用：最小好进制

Is

计算是否存在m位 k进制的1为目标数。m位iRet 进制1大于等于目标数，可能有多个符合的iRet，取最小值。非最小值一定不是。

namespace NBinarySearch
{
	template<class INDEX_TYPE,class _Pr>
	INDEX_TYPE FindFrist(INDEX_TYPE left, INDEX_TYPE rightInclue, _Pr pr)
	{
		while (rightInclue - left > 1)
		{
			const auto mid = left + (rightInclue - left) / 2;
			if (pr(mid))
			{
				rightInclue = mid;
			}
			else
			{
				left = mid;
			}
		}
		return rightInclue;
	}

	template<class INDEX_TYPE, class _Pr>
	INDEX_TYPE FindEnd(INDEX_TYPE leftInclude, INDEX_TYPE right, _Pr pr)
	{
		while (right - leftInclude > 1)
		{
			const auto mid = leftInclude + (right - leftInclude) / 2;
			if (pr(mid))
			{
				leftInclude = mid;
			}
			else
			{
				right = mid;
			}
		}
		return leftInclude;
	}
}

class Solution {
public:
	string smallestGoodBase(string n) {
		long long llN = 0;
		for (const auto& ch : n)
		{
			llN = (llN * 10 + ch - '0');
		}
		for (int i = 70; i > 2; i--)
		{
			long long llRet = Is(i, llN);
			if (llRet > 0)
			{
				return std::to_string(llRet);
			}
		}
		return std::to_string(llN - 1);
	}
	long long Is(int m, long long n)
	{
		int iRet = NBinarySearch::FindEnd(2LL, n + 1LL, [&](const auto mid) {return Cmp(mid, m, n) >= 0; });
		return (0 == Cmp(iRet,m,n))? iRet : 0;
	}
	//k进制的m个1和n的大小比较,n大返回正数，相等返回0，n小返回负数
	long long Cmp(long long k, int m, long long n)
	{
		long long llHas = 1;
		for (; m > 0; m--)
		{
			if (n < llHas)
			{
				return -1;
			}
			n -= llHas;
			if (m > 1)
			{// 最后一次llHas并不使用，所以越界不影响
				if (LLONG_MAX / k < llHas)
				{
					return -1;
				}
				llHas *= k;
			}
		}
		return n;
	}
};

template<class T>
void Assert(const T& t1, const T& t2)
{
	assert(t1 == t2);
}

template<class T>
void Assert(const vector<T>& v1, const vector<T>& v2)
{
	if (v1.size() != v2.size())
	{
		assert(false);
		return;
	}
	for (int i = 0; i < v1.size(); i++)
	{
		Assert(v1[i], v2[i]);
	}
}

int main()
{
	Solution slu;
	string res;
	res = slu.smallestGoodBase("470988884881403701");
	Assert(res, std::string("686286299"));
	res = slu.smallestGoodBase("2251799813685247");
	Assert(res, std::string("2"));
	res = slu.smallestGoodBase("13");
	Assert(res, std::string("3"));
	res = slu.smallestGoodBase("4681");
	Assert(res, std::string("8"));
	res = slu.smallestGoodBase("1000000000000000000");
	Assert(res, std::string("999999999999999999"));
	res = slu.smallestGoodBase("1333");
	Assert(res, std::string("36"));
	res = slu.smallestGoodBase("463381");
	Assert(res, std::string("463380"));

	//CConsole::Out(res);
}

扩展阅读

视频课程

有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771

如何你想快

速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

相关下载

想高屋建瓴的学习算法，请下载《喜缺全书算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653

我想对大家说的话
闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛

测试环境

操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。


http://lihuaxi.xjx100.cn/news/1898652.html

相关文章

设计模式—装饰模式

设计模式—装饰模式

与其明天开始&#xff0c;不如现在行动&#xff01; 文章目录 装饰模式—穿衣服&#x1f48e;总结 装饰模式—穿衣服 装饰模式&#xff08;Decorator&#xff09;可以动态的给对象添加一些额外的职责。 Component是定义一个对象接口&#xff0c;可以给这些对象动态地添加职责。…
阅读更多...
HPV治疗期间如何预防重复感染？谭巍主任讲述具体方法

HPV治疗期间如何预防重复感染？谭巍主任讲述具体方法

众所周知&#xff0c;人乳头瘤病毒(HPV)是一种常见的性传播疾病&#xff0c;感染后可能会引起生殖器疣、宫颈癌等疾病。在治疗期间&#xff0c;预防重复感染非常重要。今日将介绍一些预防HPV重复感染的方法。 1. 杜绝不洁性行为 在治疗期间&#xff0c;患者应该避免与感染HPV…
阅读更多...
FLStudio2024完整版水果音乐编曲制作软件

FLStudio2024完整版水果音乐编曲制作软件

FL Studio2024是款专业的音频录制编辑软件&#xff0c;可以针对作曲者的要求编辑出不同音律的节奏&#xff0c;例如鼓、镲、锣、钢琴、笛、大提琴等等任何乐器的节奏律动。FL Studio目前在中国已经受到广大制作人喜爱&#xff0c;使用它制作的音乐作品也已经数不胜数&#xff0…
阅读更多...
下午好~ 我的论文【CV边角料】（第三期）

下午好~ 我的论文【CV边角料】（第三期）

文章目录 CV边角料Pixel ShuffleSENetCBAMGlobal Context Block (GC)Criss-Cross Attention modules (CC) CV边角料 Pixel Shuffle Real-Time Single Image and Video Super-Resolution Using an Efficient Sub-Pixel Convolutional Neural Network pixelshuffle算法的实现流…
阅读更多...
为什么Apache Doris适合做大数据的复杂计算，MySQL不适合？

为什么Apache Doris适合做大数据的复杂计算，MySQL不适合？

为什么Apache Doris适合做大数据的复杂计算&#xff0c;MySQL不适合&#xff1f; 一、背景说明二、DB架构差异三、数据结构差异四、存储结构差异五、总结 一、背景说明 经常有小伙伴发出这类直击灵魂的疑问&#xff1a; Q&#xff1a;“为什么Apache Doris适合做大数据的复杂计…
阅读更多...
【漏洞复现】系列集合

【漏洞复现】系列集合

该篇文章仅供学习网络安全技术参考研究使用&#xff0c;请勿使用相关技术做违法操作 Apache Apache_HTTPD_未知后缀名解析Apache_HTTPD_换行解析(CVE-2017-15715)Apache_HTTPD_多后缀解析Apache_HTTP_2.4.50_路径穿越(CVE-2021-42013)Apache_HTTP_2.4.49_路径穿越(CVE-2021-41…
阅读更多...
【ICCV 2022】（MAE）Masked Autoencoders Are Scalable Vision Learners

【ICCV 2022】（MAE）Masked Autoencoders Are Scalable Vision Learners

何凯明一作文章&#xff1a;https://arxiv.org/abs/2111.06377 本文的出发点&#xff1a;是BERT的掩码自编码机制&#xff1a;移除一部分数据并对移除的内容进行学习。mask自编码源于CV但盛于NLP&#xff0c;恺明对此提出了疑问&#xff1a;是什么导致了掩码自编码在视觉与语言…
阅读更多...
【手撕算法系列】BN

【手撕算法系列】BN

BN的计算公式 BN中均值与方差的计算 所以对于输入x: b,c,h,w 则 mean: 1,c,1,1var: 1,c,1,1代码 class BatchNorm(nn.Module):def __init__(self, num_features, num_dims):# num_features&#xff1a;完全连接层的输出数量或卷积层的输出通道数。# num_dims&#xff1a;2表示…
阅读更多...
最新文章

Copyright @ 2022~2023