首页 > 其他分享 >二分详解——学习笔记

二分详解——学习笔记

时间:2024-09-17 16:02:23浏览次数:10  
标签:二分 布尔值 mid 笔记 详解 答案 例题 check

首先,使用二分有几个前提:

  • 具有单调性

  • 要求“最小的最大”或“最大的最小”

其次,还要分清楚二分查找与二分答案的区别:

  • 二分查找:在某区间使用二分的思想进行查找

  • 二分答案:在答案的区间中使用二分的思想并判断从而找到最优解

同时还要处理好二分的边界。

接下来来理解一下二分法的思想

每次都有一个左端点 \(l\) 和右端点 \(r\),然后判断这一段选中区间的中点 \(mid= \frac {(l+r)}{2}\) 是否满足条件,若满足则结束搜索;否则到这个中点的左侧/右侧寻找答案。因为二分每次查找的区间都是上一次的一半,所以最劣时间复杂度是 \(O(log_2(n))\) 的。

然后来看一下模版代码

先说明一下,\(x>>y\) 是位运算,意思是把 \(x\) 在二进制下右移 \(y\) 位,即 \(\lfloor \frac {x}{2^y} \rfloor\),左移 \(y\) 位则是 \(x<<y\),即 \(x \times 2^y\),这样会比直接使用 \(/\) 的效率更快,快读中的 \(ans=(ans<<3)+(ans<<1)+x\) 也是同样的道理。

  1. 使找到的答案尽可能靠左(即在一个升序排列中要求“最小的最大”)
python
while l<r:
  mid=(l+r)>>1 #or (l+r)//2
  if check(mid): #check 应为判断函数,并且应该返回一个布尔值
    r=mid
  else:
    l=mid+1
c++
while(l<r){
  int mid=(l+r)>>1; //or (l+r)/2
  if(check(mid)) r=mid; //check 应为判断函数,并且应该返回一个布尔值
  else l=mid+1;
}
  1. 使找到的答案尽可能靠右(即在一个升序排列中要求“最大的最小”)
python
while l<r:
  mid=(l+r+1)>>1 #or (l+r+1)//2
  if check(mid): #check 应为判断函数,并且应该返回一个布尔值
    l=mid
  else:
    r=mid-1
c++
while(l<r){
  int mid=(l+r+1)>>1; //or (l+r+1)/2
  if(check(mid)) l=mid; //check 应为判断函数,并且应该返回一个布尔值
  else r=mid-1;
}

接下来是二分答案

什么时候需要二分答案?

答案在一个很大的区间中,暴力会超时,这时就要使用二分答案了。

那怎么做呢?

首先要确定好初始范围,然后根据题意写一个 \(check\) 判断函数,最后看到底是“最小的最大”还是“最大的最小”从而套用模板。

一些例题

例题一

例题二

例题三

例题四

标签:二分,布尔值,mid,笔记,详解,答案,例题,check
From: https://www.cnblogs.com/xzq4121/p/18417217/erfen

相关文章

  • Maven笔记(二):进阶使用
    Maven笔记(二)-进阶使用一、Maven分模块开发分模块开发对项目的扩展性强,同时方便其他项目引入相同的功能。将原始模块按照功能拆分成若干个子模块,方便模块间的相互调用,接口共享(类似Jar包一样之间引用、复用)。开发步骤:创建Maven项目书写模块代码分模块开发需要先针对......
  • 跟着问题学10——RNN详解及代码实战
    1循环神经网络RecurrentNeuralNetwork什么是序列信息呢?通俗理解就是一段连续的信息,前后信息之间是有关系地,必须将不同时刻的信息放在一起理解。比如一句话,虽然可以拆分成多个词语,但是需要将这些词语连起来理解才能得到一句话的意思。RNN就是用来处理这些序列信息的任务......
  • 【软考】进制转换笔记
    学习参考:https://www.bilibili.com/video/BV1rc411t71D?p=2一、十进制数74356.234 按十进制算法为 整数部分:7 位权为数4,4 位权数为3,3位权数为2,5位权数为1,6位权数为0小数部分:2 位权数为-1,3 位权数为-2,4位权数-3进制为10,公式是 进制N的位权数次方所得整......
  • 【MySQL】MySQL中JDBC编程——MySQL驱动包安装——(超详解)
    前言:......
  • 指针详解(中秋版)
       久违的键盘声,熟悉的思绪,仿佛时间在这一刻凝固。距离我上一次敲击键盘写下文字,已不知过了多少个日夜。但文字的魅力就在于,它总能跨越时间的长河,将我们的心灵再次相连。今天,我带着满心的感慨与新的故事,重新坐到了屏幕前。让我们一起,再次启程,探索文字的奥秘。(一)理解......
  • 代码整洁之道--读书笔记(11)
    代码整洁之道简介:本书是编程大师“Bob大叔”40余年编程生涯的心得体会的总结,讲解要成为真正专业的程序员需要具备什么样的态度,需要遵循什么样的原则,需要采取什么样的行动。作者以自己以及身边的同事走过的弯路、犯过的错误为例,意在为后来者引路,助其职业生涯迈上更高台阶。本......
  • 基于django+vue高校笔记分享系统【开题报告+程序+论文】-计算机毕设
    本系统(程序+源码+数据库+调试部署+开发环境)带论文文档1万字以上,文末可获取,系统界面在最后面。系统程序文件列表开题报告内容研究背景在信息化高速发展的今天,高等教育领域正经历着前所未有的变革。随着知识更新速度的加快和在线学习平台的兴起,学生们对于高效获取、整理与分......
  • 【学习笔记】欧拉线性筛
    欧拉线性筛简介欧拉线性筛主要用于求\(n\)以内的所有素数,时间复杂度为\(O(n)\)算法实现欧拉线性筛的原理是保证\(n\)以内的所有素数只被他所含有的最小质因子筛过,这样就使得每个素数只被筛过了一次。我们设一个数组\(prime[i]\)表示第\(i\)个素数是多少,\(is\_prime[i]\)表示......
  • 【学习笔记】扩展欧几里得
    扩展欧几里得算法(exgcd)简介扩展欧几里得算法基于辗转相除法构建,主要用于求方程\[ax+by=c\]最小正整数解步骤1.求方程\(ax+by=gcd(a,b)\)的解我们构造两个方程\[\begin{cases}ax+by=gcd(a,b)\\bx'+(a\%b)y'=gcd(b,a\%b)\end{cases}\]因为由欧几里得算法易于得到\[gc......
  • CMake构建学习笔记17-uriparser库的构建和使用
    在连续论述了几篇关于CMake如何使用的文章之后,笔者也是感觉被掏空了。接下来几篇就还是回到构建依赖库的问题上,容笔者花时间找到更好的主题来介绍更多关于CMake使用干货。如何有的读者自信已经很熟悉这方面的知识,可以进行跳过,在需要的时候再进行查阅。uriparser是一个严格遵循RFC......