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

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<iostream>

1. 在a中找

2、实数域

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

---

B二分判定

占坑待填