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

2023-12-17 19:28

本文主要是介绍【二分查找】自写二分函数的总结,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

作者推荐

【动态规划】【广度优先搜索】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://www.chinasem.cn/article/505554

相关文章

MySQL 字符串截取函数及用法详解

《MySQL字符串截取函数及用法详解》在MySQL中,字符串截取是常见的操作,主要用于从字符串中提取特定部分,MySQL提供了多种函数来实现这一功能,包括LEFT()、RIGHT()、SUBST... 目录mysql 字符串截取函数详解RIGHT(str, length):从右侧截取指定长度的字符SUBST

C#实现查找并删除PDF中的空白页面

《C#实现查找并删除PDF中的空白页面》PDF文件中的空白页并不少见,因为它们有可能是作者有意留下的,也有可能是在处理文档时不小心添加的,下面我们来看看如何使用Spire.PDFfor.NET通过C#... 目录安装 Spire.PDF for .NETC# 查找并删除 PDF 文档中的空白页C# 添加与删

Linux区分SSD和机械硬盘的方法总结

《Linux区分SSD和机械硬盘的方法总结》在Linux系统管理中,了解存储设备的类型和特性是至关重要的,不同的存储介质(如固态硬盘SSD和机械硬盘HDD)在性能、可靠性和适用场景上有着显著差异,本文... 目录一、lsblk 命令简介基本用法二、识别磁盘类型的关键参数:ROTA查询 ROTA 参数ROTA

Kotlin运算符重载函数及作用场景

《Kotlin运算符重载函数及作用场景》在Kotlin里,运算符重载函数允许为自定义类型重新定义现有的运算符(如+-…)行为,从而让自定义类型能像内置类型那样使用运算符,本文给大家介绍Kotlin运算... 目录基本语法作用场景类对象数据类型接口注意事项在 Kotlin 里,运算符重载函数允许为自定义类型重

Pandas中统计汇总可视化函数plot()的使用

《Pandas中统计汇总可视化函数plot()的使用》Pandas提供了许多强大的数据处理和分析功能,其中plot()函数就是其可视化功能的一个重要组成部分,本文主要介绍了Pandas中统计汇总可视化... 目录一、plot()函数简介二、plot()函数的基本用法三、plot()函数的参数详解四、使用pl

Qt实现网络数据解析的方法总结

《Qt实现网络数据解析的方法总结》在Qt中解析网络数据通常涉及接收原始字节流,并将其转换为有意义的应用层数据,这篇文章为大家介绍了详细步骤和示例,感兴趣的小伙伴可以了解下... 目录1. 网络数据接收2. 缓冲区管理(处理粘包/拆包)3. 常见数据格式解析3.1 jsON解析3.2 XML解析3.3 自定义

Python的time模块一些常用功能(各种与时间相关的函数)

《Python的time模块一些常用功能(各种与时间相关的函数)》Python的time模块提供了各种与时间相关的函数,包括获取当前时间、处理时间间隔、执行时间测量等,:本文主要介绍Python的... 目录1. 获取当前时间2. 时间格式化3. 延时执行4. 时间戳运算5. 计算代码执行时间6. 转换为指

Python正则表达式语法及re模块中的常用函数详解

《Python正则表达式语法及re模块中的常用函数详解》这篇文章主要给大家介绍了关于Python正则表达式语法及re模块中常用函数的相关资料,正则表达式是一种强大的字符串处理工具,可以用于匹配、切分、... 目录概念、作用和步骤语法re模块中的常用函数总结 概念、作用和步骤概念: 本身也是一个字符串,其中

Python实现图片分割的多种方法总结

《Python实现图片分割的多种方法总结》图片分割是图像处理中的一个重要任务,它的目标是将图像划分为多个区域或者对象,本文为大家整理了一些常用的分割方法,大家可以根据需求自行选择... 目录1. 基于传统图像处理的分割方法(1) 使用固定阈值分割图片(2) 自适应阈值分割(3) 使用图像边缘检测分割(4)

Windows Docker端口占用错误及解决方案总结

《WindowsDocker端口占用错误及解决方案总结》在Windows环境下使用Docker容器时,端口占用错误是开发和运维中常见且棘手的问题,本文将深入剖析该问题的成因,介绍如何通过查看端口分配... 目录引言Windows docker 端口占用错误及解决方案汇总端口冲突形成原因解析诊断当前端口情况解