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

作者推荐

【动态规划】【广度优先搜索】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++**实现。

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/252823.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

力扣刷题-二叉树-平衡二叉树

力扣刷题-二叉树-平衡二叉树

110 平衡二叉树 给定一个二叉树&#xff0c;判断它是否是高度平衡的二叉树。 本题中&#xff0c;一棵高度平衡二叉树定义为&#xff1a;一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。 示例 1: 给定二叉树 [3,9,20,null,null,15,7] 返回 true 。 给定二叉树 [1…
阅读更多...
AUTOSAR ComM模块配置以及代码

AUTOSAR ComM模块配置以及代码

ComM模块配置以及代码执行流程 1、基本的一个通道的配置列表 ComMNmVariant 概念的个人理解&#xff1a; FULL&#xff1a; 完全按照AUTOSAR NM方式进行调用 LIGHT &#xff1a;设置一个超时时间&#xff0c;在请求停止通信的时候开始计时&#xff0c;超时之后才会进入FULLCOM…
阅读更多...
运维实践｜采集MySQL数据出现many connection errors

运维实践｜采集MySQL数据出现many connection errors

文章目录 问题出现问题分析当前环境问题分析 解决方案1 检查调度事件任务是否开启2 开启调度事件任务3 创建一张日志表4 创建函数存储过程5 创建事件定时器6 开启事件调度任务7 检查核实是否创建 总结 问题出现 最近在做OGG结构化数据采集工作&#xff0c;在数据采集过程中&am…
阅读更多...
将博客搬至微信公众号了

将博客搬至微信公众号了

一、博客搬家通知 各位码友们好&#xff0c;大家是不是基本很少看 CSDN 了呢&#xff1f;平时开发是不都依靠着 chatGPT 来解决工作中的技术问题了&#xff0c;不过我觉得在工作中的使用场景各式各样的&#xff0c;具体问题还得自己具体去梳理逻辑&#xff0c;再考虑用什么样的…
阅读更多...
C语言：求和1+1/2-1/3+1/4-1/5+……-1/99+1/100

C语言：求和1+1/2-1/3+1/4-1/5+……-1/99+1/100

#include<stdio.h> int main() {int i 0;double sum 0.0;int flag 1;for (i 1;i < 100;i){sum 1.0 / i * flag;flag -flag;}printf("sum%lf\n", sum);return 0; }
阅读更多...
SpringIOC之@Primary

SpringIOC之@Primary

博主介绍&#xff1a;✌全网粉丝5W&#xff0c;全栈开发工程师&#xff0c;从事多年软件开发&#xff0c;在大厂呆过。持有软件中级、六级等证书。可提供微服务项目搭建与毕业项目实战&#xff0c;博主也曾写过优秀论文&#xff0c;查重率极低&#xff0c;在这方面有丰富的经验…
阅读更多...
力扣刷题-二叉树-找树左下角的值

力扣刷题-二叉树-找树左下角的值

513 找树左下角的值 给定一个二叉树的 根节点 root&#xff0c;请找出该二叉树的 最底层 最左边 节点的值。 假设二叉树中至少有一个节点。 示例 1&#xff1a; 示例 2&#xff1a; 思路 层序遍历 直接层序遍历&#xff0c;因为题目说了是最底层&#xff0c;最左边的值&a…
阅读更多...
【数据结构—队列的实现】

【数据结构—队列的实现】

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 前言 一、队列 1.1队列的概念及结构 二、队列的实现 2.1头文件的实现—Queue.h 2.2源文件的实现—Queue.c 2.3源文件的测试—test.c 三、测试队列实际数据的展示 3.…
阅读更多...
mysql使用st_distance_sphere函数报错Incorrect arguments to st_distance_sphere

mysql使用st_distance_sphere函数报错Incorrect arguments to st_distance_sphere

前言 最近使用空间点位查询数据时函数报错Incorrect arguments to st_distance_sphere报错。 发现问题 因为之前是没有问题的&#xff0c;所以把问题指向了数据&#xff0c;因为是外部数据&#xff0c;不是通过系统打点获取&#xff0c;发现是因为经纬度反了&#xff0c;loc…
阅读更多...
VRRP(虚拟路由冗余协议)

VRRP(虚拟路由冗余协议)

一.VRRP简介 1.VRRP是什么 Virtual route Redundancy Protocol&#xff0c;也叫虚拟路由器冗余协议。 利用VRRP&#xff0c;一组路由器协同工作&#xff0c;单只有一个处于Master状态&#xff0c;处于该状态的路由器&#xff08;的接口&#xff09;承担实际的数据流量转发任…
阅读更多...
MapReduce序列化实例代码

MapReduce序列化实例代码

1 &#xff09;需求&#xff1a;统计每个学号该月的超市消费、食堂消费、总消费 2 &#xff09;输入数据格式 序号 学号 超市消费 食堂消费 18 202200153105 8.78 12 3 &#xff09;期望输出格式 key &#xff08;学号&#xff09; value &#xff08; bean 对象&#xf…
阅读更多...
二分查找算法的概念、原理、效率以及使用C语言循环和数组的简单实现

二分查找算法的概念、原理、效率以及使用C语言循环和数组的简单实现

二分查找的概念 二分查找也称折半查找&#xff08;Binary Search&#xff09;&#xff0c;它是一种效率较高的查找方法。但是&#xff0c;折半查找要求线性表必须采用顺序存储结构&#xff0c;而且表中元素按关键字有序排列。 实现原理 首先&#xff0c;假设表中元素是按升序…
阅读更多...
深度学习项目实战：垃圾分类系统

深度学习项目实战：垃圾分类系统

简介&#xff1a; 今天开启深度学习另一板块。就是计算机视觉方向&#xff0c;这里主要讨论图像分类任务–垃圾分类系统。其实这个项目早在19年的时候&#xff0c;我就写好了一个版本了。之前使用的是python搭建深度学习网络&#xff0c;然后前后端交互的采用的是java spring …
阅读更多...
VLAN间的通讯---三层交换

VLAN间的通讯---三层交换

一.三层交换 1.概念 使用三层交换技术实现VLAN间通信 三层交换二层交换 三层转发 2.基于CEF的MLS CEF是一种基于拓补转发的模型 转发信息库&#xff08;FIB&#xff09;临接关系表 转发信息库&#xff08;FIB&#xff09;可以理解为路由表 邻接关系表可以理解为MAC地址表…
阅读更多...
js获取日期

js获取日期

目录 Date 对象 1. 获取当前时间 2. 获取特定日期时间 Date 对象的方法 1. 获取各种日期时间组件 2. 获取星期几 3. 获取时间戳 格式化日期时间 1. 使用 toLocaleString() 方法 2. 使用第三方库 UNIX 时间戳 内部表示 时区 Date 对象 JavaScript中内置的 Date 对象…
阅读更多...
【sqli靶场】第六关和第七关通关思路

【sqli靶场】第六关和第七关通关思路

目录 前言 一、sqli靶场第六关 1.1 判断注入类型 1.2 观察报错 1.3 使用extractvalue函数报错 1.4 爆出数据库中的表名 二、sqli靶场第七关 1.1 判断注入类型 1.2 判断数据表中的字段数 1.3 提示 1.4 构造poc爆库名 1.5 构造poc爆表名 1.6 构造poc爆字段名 1.7 构造poc获取账…
阅读更多...
MySQL 报错 You can‘t specify target table for update in FROM clause解决办法

MySQL 报错 You can‘t specify target table for update in FROM clause解决办法

You can’t specify target table for update in FROM clause 其含义是&#xff1a;不能在同一表中查询的数据作为同一表的更新数 单独执行复合查询是正常的&#xff0c;如下&#xff1a; 但是当执行子查询删除命令时&#xff0c;报如下错误 DELETE FROM abpusers WHERE Id I…
阅读更多...
SLAM学习笔记001

SLAM学习笔记001

当向机器人下达移动到地点B的命令后&#xff0c;机器人不免会问三个颇具哲学性的问题&#xff0c;即“我在哪儿”“我将到何处去”“我该如何去”。slam导航技术涵盖&#xff1a;航天、军事、特种作业、工业生产、智慧交通、消费娱乐等slam导航的经典应用&#xff1a;火星探测车…
阅读更多...
vue3父组件调用子组件el-dialog对话框

vue3父组件调用子组件el-dialog对话框

vue3父组件调用子组件el-dialog对话框 在写项目的时候&#xff0c;经常要使用父子组件通讯&#xff0c;我已经写了很多篇博客来介绍父子组件通讯了&#xff0c;vue中的父子组件通讯方式有差不多10来种&#xff0c;最常用的就那么一两种&#xff0c;这里我介绍其中我认为最基础…
阅读更多...
【计算机网络】—— 详解码元，传输速率的计算|网络奇缘系列|计算机网络

【计算机网络】—— 详解码元，传输速率的计算|网络奇缘系列|计算机网络

&#x1f308;个人主页: Aileen_0v0&#x1f525;系列专栏: 一见倾心,再见倾城 --- 计算机网络~&#x1f4ab;个人格言:"没有罗马,那就自己创造罗马~" 目录 码元 速率和波特 思考1 思考2 思考3 带宽&#xff08;Bandwidth&#xff09; &#x1f4dd;总结 码元…
阅读更多...
最新文章

Copyright @ 2022~2023