1、二分查找
关于二分查找主要有三种模板
模板1 结束条件为 l + 1 == r
查找最后一个 <= x 数的下标 （最大化查找，可行区在左侧）
int find(int x)
{
int l = 0,r = n + 1; // 开区间,数据存储下标为1~n
while(l + 1 < r)
{
int mid = l + r >> 1;
if(a[mid] <= x) l = mid;
else r = mid;
}
return l;
}
查找第一个 >= x数的下标 （最小化查找，可行区在右侧）
int find(int x)
{
int l = 0,r = n + 1; // 开区间,数据存储下标为1~n
while(l + 1 < r)
{
int mid = l + r >> 1;
if(a[mid] >= x) r = mid;
else l = mid;
}
return r;
}
模板2 结束条件为 l == r （y总的板子）
查找最后一个 <= x 数的下标 （最大化查找，可行区在左侧）
int find(int x)
{
int l = 1,r = n; // 闭区间,数据存储下标为1~n
while(l < r)
{
int mid = l + r + 1 >> 1;
if(a[mid] <= x) l = mid;
else r = mid - 1;
}
return l;
}
查找第一个 >= x数的下标 （最小化查找，可行区在右侧）
int find(int x)
{
int l = 1,r = n; // 闭区间,数据存储下标为1~n
while(l < r)
{
int mid = l + r >> 1;
if(a[mid] >= x) r = mid;
else l = mid + 1;
}
return r;
}
模板3 结束条件为 l == r +1（一个OI同学常用的板子）
查找最后一个 <= x 数的下标 （最大化查找，可行区在左侧）
int find(int x)
{
int ans = 0;
int l = 1,r = n; // 闭区间,数据存储下标为1~n
while(l <= r)
{
int mid = l + r >> 1;
if(a[mid] <= x) ans = mid,l = mid + 1;
else r = mid - 1;
}
return ans;
}
查找第一个 >= x数的下标 （最小化查找，可行区在右侧）
int find(int x)
{
int ans = 0;
int l = 1,r = n; // 闭区间,数据存储下标为1~n
while(l <= r)
{
int mid = l + r >> 1;
if(a[mid] >= x) ans = mid,r = mid - 1;
else l = mid + 1;
}
return r;
}
上面三个板子中比较好用的是第一个和第三个，第二个板子在 >= x和 <= x 的mid计算方式不同，所以在编程过程中出错的概率更大。
其中第一个板子 \(l\) 和 \(r\) 都只在各自的可行区移动，也就是说在 <= x 的情况下，下标\(l\)对应的数 一直 <= x, 下标\(r\)对应的数一直 > x
我个人比较喜欢第一个板子，接下来用第一个板子介绍一下浮点二分和二分答案。
浮点二分
double find(double x)
{
double l = 下界 - 1,r = 上界 + 1;//因为是浮点数，这里l,r不那么精确也行,可以适当扩大范围
while(r - l > 1e-5) //因为计算机的精度问题，所以两个浮点数相差1e-5就可以认为是相等的
{
double mid = (l + r) / 2;
if(check(mid)) l = mid;
else r = mid;
}
return l;
}
2、二分答案
2.1 最大化答案（可行区在左侧）
int find()
{
int l = 下界 - 1,r = 上界 + 1;
while(l + 1 < r)
{
int mid = l + r >> 1;
if(check(mid)) l = mid;
else r = mid;
}
return l;
}
2.2 最小化答案（可行区在右侧）
int find()
{
int l = 下界 - 1,r = 上界 + 1;
while(l + 1 < r)
{
int mid = l + r >> 1;
if(check(mid)) r = mid;
else l = mid;
}
return r;
}
bool check(int x)
{
//根据可行区不同，编写不同的check函数
}