【基础】二分算法学习笔记

文章目录[x]
  1. 1:A基本用法
  2. 2:B二分判定

            1、二分的基本用法是在单调序列或单调函数中进行查找。 

2、当问题的答案具有单调性时,就可以通过二分把求解转化为判定(判定一般比求解容易实现。


A基本用法

(这里都是个人写法,可以跳过

1、整数域

1)原则

  • 最终答案处于闭区间[l,r]内
  • 循环以l==r结束
  • 每次二分中间值mid归属左半端与右半段之一

2)流程

  1. 分析问题,确定左右半段哪个是可行区间,以及mid归属哪一半。
  2. 选择写法(l==mid还是r==mid…
  3. l==r时即得到答案。

3)写法

  1. 缩小范围时,r==mid,l==mid+1,取中间值时,mid=(l+r)/2;
  2. 缩小范围时,l==mid,r==mid-1,取中间值时,mid=(l+r+1)/2;

关于第二种为什么要+1,是因为当l+1==r时,mid=l+r>>1,便进入l = mid分支,区间无法缩小,成了死循环。

4)实例

  1. 在a中找
#include
  1. 在a中找

2、实数域

  1. 精度确定;eps
  2. 精度不确定;

B二分判定

占坑待填

点赞

发表评论

昵称和uid可以选填一个,填邮箱必填(留言回复后将会发邮件给你)
tips:输入uid可以快速获得你的昵称和头像