算法基础学习笔记——②二分

这篇具有很好参考价值的文章主要介绍了算法基础学习笔记——②二分。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

博主:命运之光
专栏:算法基础学习

算法基础学习笔记——②二分


前言:算法学习笔记记录日常分享,需要的看哈O(∩_∩)O,感谢大家的支持!


✨二分

🍓整数二分

1.有单调性一定可以二分,没有单调性也可能二分
2.二分的本质是边界,只要找到某种性质,使得整个区间一分为二, 那么就可以用二分把整个边界点二分出来

image.png
二分红色分界点时
image.png
解释这里为什么要+1:如果当l=r-1时, 不加1时mid=(l+r)/2=l(要下取整,1被略掉),进行if(check(mid))如果为 true,则更新l=mid,可此时mid算出还是=l,故进入死循环)
此处check是否满足红色性质
image.png
区间[l, r]被划分成[l, mid -1]和[mid, r]时使用:

int bsearch_2(int l, int r){
    while (l < r)
        {
            int mid = l + r + 1 >> 1;
            if (check(mid)) l = mid;
            else r = mid -1;
        }
    return l;
}

image.png
此处check是否满足绿色性质
image.png
区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用:

int bsearch_1(int l, int r){
	while (l < r)
    {
        int mid = l + r >> 1;
        if (check(mid)) r = mid;    // check()判断mid是否满足性质
        else l = mid + 1;
    }
    return l;
}

简单理解:mid的值不在所求答案区间(故找答案区间旁边的区间求mid的值)

🍓整数二分模板:

bool check(int x) {/* ... */} // 检查x是否满足某种性质
// 区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用:
int bsearch_1(int l, int r)
{
	while (l < r)
    {
        int mid = l + r >> 1;
        if (check(mid)) r = mid;    // check()判断mid是否满足性质
        else l = mid + 1;
    }
    return l;
}
// 区间[l, r]被划分成[l, mid -1]和[mid, r]时使用:
int bsearch_2(int l, int r)
{
	while (l < r)
    {
        int mid = l + r + 1 >> 1;
        if (check(mid)) l = mid;
        else r = mid -1;
    }
    return l;
}

//关于while的理解:
while (l < r)
{
int mid = l + r >> 1;
if (check(mid)) r = mid;
else l = mid + 1;
}
eg. 1 2 4 5 6 中查找3(答案没有)
每个数字的标号:0 1 2 3 4
第一次进入while循环:
mid=(0+4)/2=2,q[mid]=4;
If(q[mid]>=3)r=mid=2;
第二次进while循环:
mid=(0+2)/2=1,q[mid]=2;
if(q[mid]>=3)r=mid;
显然q[mid]❤️,
else l=mid+1=2;
现在l=r=2进入不了循环且q[l]!=3,(这里q[l]=q[r]就是最终二分彻底的值故没有找到3

🍓浮点数二分

image.png
当l~r足够小(≤[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-H8YrNrO8-1685067877207)(null#card=math&code=10^{-6}&id=a4G1L)])就可以用l或r当作答案

🍓浮点数二分模板

bool check(double x) {/* ... */} // 检查x是否满足某种性质
double bsearch_3(double l, double r)
{
    const double eps = 1e-6;   // eps 表示精度,取决于题目对精度的要求
	while (r -l > eps)//写法2:for(int i=0;i<100;i++)   //不用精度,直接循环100次也可以
    {
        double mid = (l + r) / 2;//注意:这里不能写>>1,int时可进行>>1操作
        if (check(mid)) r = mid;
        else l = mid;
    } 
    return l;
}

小贴士:
image.png

🍓整数二分步骤:

1.找一个区间[L,R],使得答案一定在该区间中;
2.找一个判断条件,使得该判断条件具有二段性,并且答案一定是该二段性的分界点;
3.分析终点M在该判断条件下是否成立,如果成立,考虑答案在哪个区间:如果不成立,考虑答案在哪个区间;
4.如果更新方式写的是R=Mid,则不用做任何处理;如果更新方式写的是L=Mid,则需要在计算Mid时加上1。

遇见二分先画图文章来源地址https://www.toymoban.com/news/detail-493933.html

🍓二分模板2:

int 1=1,r=n,res;
while(1<=r)
{
    int mid=(1+r)/2;
    if(check(mid))
    {
        r=mid-1;
        res=mid;
    }
    else l=mid+1;
}
while(1<=r)
{
    int mid=(1+r)/2;
    if(check(mid))
    {
        1=mid+1;
        res=mid;
    }
    else r=mid-1;
}

到了这里,关于算法基础学习笔记——②二分的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 二分、三分算法笔记

    目录 什么是二分 举例 代码模型 不足 改进代码 例题 题目描述 输入格式 输出格式

    2024年01月17日
    浏览(13)
  • 算法笔记:二分查找

    1.1 概念 二分查找也称折半查找(Binary Search),它是一种效率较高的查找方法。但是,折半查找要求线性表必须采用顺序存储结构,而且表中元素按有序排列。 二分查找维护查找空间的左、右和中间指示符,并比较查找目标或将查找条件应用于集合的中间值;如果条件

    2024年02月04日
    浏览(45)
  • 【基础算法练习】二分模板

    704. 二分查找,这道题目是最经典的二分查找,使用于任何模板(如果你学的模板连这道题都套不上,那大概是模板有问题) 34. 在排序数组中查找元素的第一个和最后一个位置,一个合格的二分模板,需要能够应对这道题目的两种二分情况,我待会儿也会以这道题作为例题

    2024年01月25日
    浏览(11)
  • 【算法基础:搜索与图论】3.6 二分图(染色法判定二分图&匈牙利算法)

    https://oi-wiki.org/graph/bi-graph/ 二分图是图论中的一个概念, 它的所有节点可以被分为两个独立的集合,每个边的两个端点分别来自这两个不同的集合 。 换句话说, 二分图中不存在连接同一集合内两个节点的边 。 如何判断一个图是二分图? 当且仅当图中不含奇数环 。(奇数

    2024年02月16日
    浏览(17)
  • 算法基础学习笔记——①排序

    ✨ 博主:命运之光 ✨ 专栏: 算法基础学习 前言: 算法学习笔记记录日常分享,需要的看哈O(∩_∩)O,感谢大家的支持! 因为x参与交换之后仍然会被留在左右区间中的一个里。 1.确定分界点:(这里的分界点不一定是x,可以随意取值,常用取值方法如下) q[l],q[(l+r)/2],q[r],随机

    2024年02月07日
    浏览(15)
  • 【algorithm】算法基础课---二分查找算法(附笔记 | 建议收藏)

    🚀write in front🚀 📝个人主页:认真写博客的夏目浅石. 🎁欢迎各位→点赞👍 + 收藏⭐️ + 留言📝 📣系列专栏:AcWing算法学习笔记 💬总结:希望你看完之后,能对你有所帮助,不足请指正!共同学习交流 🖊 ✉️ 如果无聊的话,就来逛逛我的博客栈吧 stack-frame.cn 关于我

    2024年01月18日
    浏览(12)
  • 二分算法学习

    🌼 扎着马尾的姑娘,笑容温柔很善良 自在的少年 - 要不要买菜 - 单曲 - 网易云音乐 前言 本来打算做 蓝桥杯 2022C++A组省赛F题 青蛙过河 的,看到标签显示\\\" 二分 \\\",第一时间竟然想不到二分是什么,所以来学习下 目录 🌼二分是什么  🌼一,砍树 🌼二,手写快排 🌼三,阶

    2023年04月12日
    浏览(8)
  • 【OI学习笔记】基础算法-前缀和与差分算法

    板块:基础算法、线性优化 难度:较易 前置知识:C++基础语法 在一维空间中,对于一个数据总量为 n n n 的数组 a a a ,有数据 a [ 1 ] , a [ 2 ] , a [ 3 ] , . . . , a [ n − 1 ] , a [ n ] a[1],a[2],a[3],...,a[n-1],a[n] a [ 1 ] , a [ 2 ] , a [ 3 ] , ... , a [ n − 1 ] , a [ n ] ,定义一个数组 s u m sum s u m ,

    2024年02月08日
    浏览(15)
  • 【密码学基础】半/全同态加密算法基础学习笔记

    定义:只支持乘法或加法中的一种的同态加密。同态加密指的是允许直接对密文进行计算,密文计算结果解密后与明文直接计算结果相同。 Paillier加解密过程 Paillier的同态性 明文加法 = 密文乘法 明文乘法 = 密文指数幂 Paillier的安全性 基于大整数分解困难问题 相比Paillier,

    2024年02月13日
    浏览(16)
  • 动态规划——带权二分优化DP 学习笔记

    带权二分其实并不一定用于优化 DP,也可能用于优化贪心等最优化的算法。 带权二分也叫 WQS 二分,最初由王钦石在他的 2012 年国家集训队论文中提出。 使用情况 要解决一个最优化问题(求最大 / 最小值) 有一个限制,一般是某个参数要求一定恰好为 (k) 而带权二分就可以

    2024年02月08日
    浏览(17)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包